10

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

Johnny
  • 101
  • 1
  • 3

3 Answers3

14

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.

Jeffrey
  • 1,681
  • 3
  • 13
  • 23
  • 5
    To put a name on it: This is a well-known algorithm, known as [Reservoir sampling](http://en.wikipedia.org/wiki/Reservoir_sampling). – Joey Jul 17 '10 at 22:53
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.

eruciform
  • 7,680
  • 1
  • 35
  • 47
-1

Just do for each node a random call in the range 0 up to (number of childs)-1 and select the next child after that number.

Repeat this until you are in a leaf.

Quonux
  • 2,975
  • 1
  • 24
  • 32
  • This will be biased towards nodes at upper levels of the tree. For example, the probability of selecting the rootNode = 1/3 (assuming a max of 2 children). The probability of selecting the leftmost leaf node = (1/3)^k, where k = depth of the leaf node. – Menezes Sousa Nov 18 '15 at 17:21
  • this is true, however, in some instances it doesn't matter but thx for pointing this out – Quonux Nov 19 '15 at 20:19