CODEWITHSUNDEEP
randomtree
Johnny
Johnny

Reputation: 101

How to pick a random node from a tree

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

Upvotes: 10

Views: 2788

Answers (3)

eruciform
eruciform

Reputation: 7736

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.

Upvotes: 2

Jeffrey
Jeffrey

Reputation: 1689

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.

Upvotes: 14

Quonux
Quonux

Reputation: 2991

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.

Upvotes: -1

Related Questions