Select a Node at Random from Unbalanced Binary Tree

Question

One of my friends had the following interview question, and neither of us are quite sure what the correct answer is. Does anyone have an idea about how to approach this?

Given an unbalanced binary tree, describe an algorithm to select a node at random such that each node has an equal probability of being selected.

Answer 1

You can do it with a single pass of the tree. The algorithm is the same as with a list.

When you see the first item in the tree, you set it as the selected item.

When you see the second item, you pick a random number in the range (0,2]. If it's 1, then the new item becomes the selected item. Otherwise you skip that item.

For each node you see, you increase the count, and with probability 1/count, you select it. So at the 101st node, you pick a random number in the range (0,101]. If it's 100, that node is the new selected node.

When you're done traversing the tree, return the selected node. The operation is O(n) in time, with n being the number of nodes in the tree, and O(1) in space. No preprocessing required.

Answer 2

We can do this recursively in one parse by selecting the random node while parsing the tree and counting the number of nodes in left and right sub tree. At every step in recursion, we return the number of nodes at the root and a random node selected uniformly randomly from nodes in sub tree rooted at root.

Let's say number of nodes in left sub tree is n_l and number of nodes in right sub tree is n_r. Also, randomly selected node from left and right subtree be R_l and R_r respectively. Then, select a uniform random number in [0,1] and select R_l with probability n_l/(n_l+n_r+1) or select root with probability 1/(n_l+n_r+1) or select R_r with probability n_r/(n_l+n_r+1).