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