Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).
void helper(TreeNode *root, int &count, int choice) { if (root == NULL) return NULL; count++; if (rand(1,count) == 1) { choice = root; } helper(root->left,count,choice); helper(root->right,count,choice);}TreeNode *findRandomNode(TreeNode *root) { TreeNode *choice = NULL; int count = 0; return helper(root,count,choice);}
http://shibaili.blogspot.com/2015/07/google-interview-questions-4.html
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.
https://www.careercup.com/question?id=13374666
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.
class TreeNode {
private int data;
public TreeNode left;
public TreeNode right;
private int size = 0;
public TreeNode(int d) {
data = d;
size = 1;
}
public TreeNode getRandomNode() {
int leftSize =left == null ? 0 left.size();
Random random = new Random();
int index = random.nextint(size);
if (index < leftSize) {
return left.getRandomNode();
} else if (index == leftSize) {
return this;
} else {
return right.getRandomNode();
}
}
public void insertinOrder(int d) {
if (d <= data) {
if (left == null) {
left = new TreeNode(d);
} else {
left.insertlnOrder( d);
}
} else {
if (right == null) {
right = new TreeNode(d);
} else {
right.insertinOrder(d);
}
}
size++;
}
public int size() {
return size;
}
public int data() {
return data;
}
public TreeNode find(int d) {
if (d == data) {
return this;
} else if (d <= data) {
return left != null ? left.find(d) : null;
} else if (d > data) {
return right != null ? right.find(d) : null;
}
return null;
}
}
Random number calls can be expensive. If we'd like, we can reduce the number of random number calls substantially.
We traversed left because we picked a number between O and 5 (inclusive). When we traverse left, we again pick a random number between O and 5. Why re-pick? The first number will work just fine.
But what if we went right instead? We have a number between 7 and 8 (inclusive) but we would need a number between O and 1 (inclusive). That's easy to fix:just subtract out LEFT SIZE + 1.
Another way to think about what we're doing is that the initial random number call indicates which node (i) to return, and then we're locating the ith node in an in-order traversal. Subtracting LEFT SIZE + 1 from i reflects that, when we go right, we skip over LEFT SIZE + 1 nodes in the in-order traversal.
class Tree {
TreeNode root= null;
public int size() {
return root == null ? 0 root.size();
}
public TreeNode getRandomNode() {
if (root == null) return null;
Random random = new Random();
int i= random.nextlnt(size());
return root.getlthNode(i);
}
public void insertinOrder(int value) {
if (root== null) {
root = new TreeNode(value);
} else {
root.insertlnOrder(value);
}
}
}
class TreeNode {
/* construc tor and variables are the same. */
public TreeNode getlthNode(int i) {
int leftSize =left== null ? 0 : left.size();
if (i < leftSize) {
return left.getithNode(i);
} else if (i == leftSize) {
return this;
} else {
33 /* Skipping over leftSize + 1 nodes, so subtract them. */
return right.getlthNode(i - (leftSize + 1));
}
}
public void insertlnOrder(int d) { /* same */
}
public int size() {
return size;
}
public TreeNode find(int d) { /* same */
}
}
https://www.careercup.com/question?id=13374666
The idea is, do a whatever order of travel, if it is the kth node we are traveling, then replace the previously selected node with probability 1/k.
== no need queue
Node* randomSelect(Node* node) {
Node* selectedNode = node;
queue.enqueue(node);
int count = 1;
while(!queue.empty()){
Node* t = queue.dequeue();
if(1.0/count >= rand())
selectedNode = t;
if(t.left != NULL)
queue.enqueue(t.left);
if(t.right != NULL)
queue.enqueue(t.right);
count++
}
return selectedNode;
}