How to pick a random node from a tree

Question

How would one go about choosing a random element from a tree? Is it necessary to know the depth/size of the tree beforehand?

Answer 1

It is not. To choose a node uniformly at random, simply iterate through the tree in any order you like. Let the nth node examined be the chosen one with probability 1/n. That is, keep a record of the node you would return in a variable, and when you look at the nth node, replace the current node with the nth one with probability 1/n. You can show by induction that this returns a node uniformly at random without needing to know how many there are beforehand.

Answer 2

If you've structured your leaves to be stored themselves within an index-able data type, like an array, then you can easily (pseudocode):

random_leaf = leaf_pile[ random( size of leaf pile ) ]

That's a nice, refreshing O(1) :-)

Of course, there may be holes, so you may have to iterate from there. If it's stored as a linked list, then you can iterate though.

Just providing an alternative to the obvious. It really depends on your data structure and your commonest-use-case.