/
RandomNode.java
95 lines (83 loc) · 1.99 KB
/
RandomNode.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package chapter04TreesAndGraphs;
import java.util.Random;
/**
*
* Problem: You are implementing a binary search tree class from scratch, which,
* in addition to insert, find, and delete, has a method getRandomNode() which
* returns a random node from the tree. All nodes should be equally likely to be
* chosen. Design and implement an algorithm for getRandomNode, and explain how
* you would implement the rest of the methods.
*
* Time Complexity: O(logN), where N is the number of nodes.
*
*/
public class RandomNode {
TreeNode root = null;
public void insertInOrder(int val) {
if (root == null) {
root = new TreeNode(val);
} else {
root.insertInOrder(val);
}
}
public int size() {
return root == null ? 0 : root.getSize();
}
public TreeNode getRandomNode() {
if (root == null) {
return null;
}
Random random = new Random();
int i = random.nextInt(size());
return root.getIthNode(i);
}
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
private int size = 0;
public TreeNode(int val) {
val = this.val;
size = 1;
}
public void insertInOrder(int val) {
if (this.val <= val) {
if (left == null) {
left = new TreeNode(this.val);
} else {
left.insertInOrder(this.val);
}
} else {
if (right == null) {
right = new TreeNode(this.val);
} else {
right.insertInOrder(this.val);
}
}
size++;
}
public int getSize() {
return size;
}
public TreeNode find(int val) {
if (this.val == val) {
return this;
} else if (this.val <= val) {
return left != null ? left.find(this.val) : null;
} else if (this.val > val) {
return right != null ? right.find(this.val) : null;
}
return null;
}
public TreeNode getIthNode(int i) {
int leftSize = left == null ? 0 : left.getSize();
if (i < leftSize) {
return left.getIthNode(i);
} else if (i == leftSize) {
return this;
} else {
return right.getIthNode(i - (leftSize + 1));
}
}
}
}