Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.