# How to pick a random node from a tree?

How can I pick a random node from a tree, given the following constraints?

• We are given the root of the tree, and at every node we are given its children nodes. But we do not know what its children nodes are unless we visit the node.
• We do not know how many nodes are in the tree or any given subtree.
• We do not know the depth of the tree.

I am trying to write a program to crawl a directory of people's names and choose a random person. The probability of choosing a given person should be 1 over the total number of people, even though I don't know the total number of people.

Thanks!

Edit: the directory has about 10 million names at most, and it's probably 2 million or less.

Edit 2: I'd like to pick 10000 names total, but if that's too computationally intensive I could do 1000 or 100.

A general easy idea to pick $k$ elements from a set of unknown size is to assign a random number from $[0,1]$ to every element, and then pick the top $k$ elements, (with regard to the assigned random numbers). It is worth noting that you want to keep only the current $k$ top entries and their assigned numbers. When a new element is found, assign it a random number (thus get $k+1$ entries) and discard the smallest (along with its assigned random number), hence obtain new $k$ top entries.

For example, to pick 2 random elements from $[A,B,C,D,E]$,

start with first $k$ elements and sort them

$[B \to 0.77, A \to 0.75]$,

add $C \to 0.40$

$[B \to 0.77, A \to 0.75, C \to 0.40]$

$[B \to 0.77, A \to 0.75]$,

add $D \to 0.04$

$[B \to 0.77, A \to 0.75, D \to 0.04]$

$[B \to 0.77, A \to 0.75]$,

add $E \to 0.95$

$[E \to 0.95, B \to 0.77, A \to 0.75]$

$[E \to 0.95, B \to 0.77]$,
Nevermind guys, I looked up "reservoir sampling." Apparently I can examine each leaf in the tree (using depth first search or something), and for the nth leaf I should select it with probability $1/n$. Stated more precisely, first we choose the first leaf in the tree. Then we replace it with the second leaf with probability $1/2$. Then we replace it with the third leaf with probability $1/3$, until we have crawled the whole tree. You can prove by induction that this selects a random leaf of the tree.