# How can one grab a random node from a binary tree without flattening it?

For practice developing algorithms, I am challenging myself to write an algorithm that picks a random node in a binary tree. I do know the number of nodes in the tree.

I can obviously do this by flattening the binary tree into a sequence (say an array) and using modulo to obtain a random index into the array.

Is there a way to grab a random node in the tree without having to turn the entire tree into an array first?

• Hmm, or what if I don't know the size of the tree? :) – David Faux Oct 15 '12 at 18:33
• This should be reducible to reservoir sampling in either case: stackoverflow.com/questions/2612648/reservoir-sampling. Note that the iterator in the code sample is abstract and can represent an arbitrary data structure. – Ganesh Oct 15 '12 at 18:44
• Also, note that reservoir sampling is linear-time in the size of your tree, and I suspect that without additional information you can't do any better, since you should be able to estimate the size of your tree by a sort of 'inverse birthday paradox' approach, counting collisions as you draw items... – Steven Stadnicki Oct 15 '12 at 21:23

Do you know how many nodes are in each node's child subtrees? If you do, you can just decide that you want, say, the $k$-th node from the left and then descend the tree to find that node:

1. Let $n$ be the total number of nodes in the tree. Choose $k$ to be a random integer between $0$ and $n-1$ inclusive. Let $A$ initially be the root node of the tree.

2. Let $m$ be the number of nodes in the left subtree of $A$. (If $A$ is a leaf or has only right children, let $m = 0$.)

3. If $k = m$, choose $A$ as the node we want and stop.

4. Otherwise, if $k < m$, replace $A$ with its left child node and repeat from step 2.

5. Otherwise (i.e. if $k > m$), subtract $m+1$ from $k$, replace $A$ with its right child node and repeat from step 2.

This algorithm is much more efficient than traversing the entire tree; its running time is bounded by the depth of the tree, which for (approximately) balanced trees is proportional to the logarithm of the total number of nodes.

• And even if you don't know the number of nodes in each subtree, you can still find the n'th without flattening the tree, by doing a depth-first search and counting nodes as you proceed. This has the same $O()$ behavior as flattening, but a much smaller constant factor. – MJD Oct 15 '12 at 22:00

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 $\frac{n_l}{(n_l+n_r+1)}$ or select root with probability $\frac{1}{n_l+n_r+1}$ or select $\frac{n_r}{n_l+n_r+1}$.