Uniform Random sampling of Unbalanced Binary Tree

Uniform Random sampling of Unbalanced Binary Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given an unbalanced binary tree, write code to select k sample node at random

straightforward solution would be to list all the nodes in any traversal order (BFS, DFS, etc) and find random k index from the n nodes in the list. But how this approach would behave if n is very large and k is very small? or n is unknown? When n is very large the probability of choosing an element from n , k/n is very very small number when n>>k. Usual method for generating (e.g. random()*(i+1) or rand()%(i+1)). is very skewed. The distribution of selection probability trends to have long negative tail. So, obviously you can't guarantee an uniform sampling.

We need to find the samples for a binary tree. Without knowing the total number of elements we can find k random sample by keeping an index starting at index=0 and increment by one whenever we come across a tree node. Using such an index we can apply reservoir sampling while traversing the tree in any traversal order as follows in O(n) time –

public static TreeNode[] randomKSampleTreeNode(TreeNode root, int k){
 TreeNode[] reservoir = new TreeNode[k];
 Queue<TreeNode> queue = new LinkedList<TreeNode>();
 queue.offer(root);
 int index = 0;
 
 //copy first k elements into reservoir 
 while(!queue.isEmpty() && index < k){
  TreeNode node = queue.poll();
  reservoir[index++] = node;
  if(node.left != null){
   queue.offer(node.left);
  }
  if(node.right != null){
   queue.offer(node.right);
  }
 }
 
 //for index k+1 to the last node of the tree select random index from (0 to index) 
 //if random index is less than k than replace reservoir node at this index by 
 //current node
 while(!queue.isEmpty()){
  TreeNode node = queue.poll();
  int j = (int) Math.floor(Math.random()*(index+1));
  index++;
  
  if(j < k){
   reservoir[j] = node;
  }
 
  if(node.left != null){
   queue.offer(node.left);
  }
  if(node.right != null){
   queue.offer(node.right);
  }
 }
 
 return reservoir;
}

http://algobox.org/random-node-in-binary-tree/

Given an unbalanced binary tree, write code to select a node at random (each node has an equal probability of being selected).

The solutions depend on the actual requirements.

---

If the query happens only one time

1. Traversal the tree using Morris Inorder Traversal and count the total number of nodes n.
2. Get a random number i in [1, n].
3. Traversal the tree using Morris Inorder Traversal and return the ith node.

The algorithm is O(n) time with O(1) extra space.

---

If the query happens many times, but tree is immutable

For a immutable tree, we can preprocess to get a direct access table to all the nodes. In other words, we create an array nodes with each element point to one unique node in the tree.
Then the query becomes:

1. Get a random number i in [0, n)
2. Return nodes[i]

The query is then O(1).

---

If the query happens many times, but tree is mutable

We can preprocess the tree with argumentation of number of nodes in the sub tree. The query is then O(h).

Read full article from Uniform Random sampling of Unbalanced Binary Tree - Algorithms and Problem SolvingAlgorithms and Problem Solving