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.
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.