How can one grab a random node from a binary tree without flattening it? For practice developing algorithms, I am challenging myself to write an algorithm that picks a random node in a binary tree. I do know the number of nodes in the tree.
I can obviously do this by flattening the binary tree into a sequence (say an array) and using modulo to obtain a random index into the array.
Is there a way to grab a random node in the tree without having to turn the entire tree into an array first?
 A: Do you know how many nodes are in each node's child subtrees?  If you do, you can just decide that you want, say, the $k$-th node from the left and then descend the tree to find that node:


*

*Let $n$ be the total number of nodes in the tree.  Choose $k$ to be a random integer between $0$ and $n-1$ inclusive.  Let $A$ initially be the root node of the tree.

*Let $m$ be the number of nodes in the left subtree of $A$.  (If $A$ is a leaf or has only right children, let $m = 0$.)

*If $k = m$, choose $A$ as the node we want and stop.

*Otherwise, if $k < m$, replace $A$ with its left child node and repeat from step 2.

*Otherwise (i.e. if $k > m$), subtract $m+1$ from $k$, replace $A$ with its right child node and repeat from step 2.
This algorithm is much more efficient than traversing the entire tree; its running time is bounded by the depth of the tree, which for (approximately) balanced trees is proportional to the logarithm of the total number of nodes.
A: We can do this recursively in one parse by selecting the random node while parsing the tree and counting the number of nodes in left and right sub tree. At every step in recursion, we return the number of nodes at the root and a random node selected uniformly randomly from nodes in sub tree rooted at root. Let's say number of nodes in left sub tree is $n_l$ and number of nodes in right sub tree is $n_r$. Also, randomly selected node from left and right subtree be $R_l$ and $R_r$ respectively. Then, select a uniform random number in [0,1] and select $R_l$ with probability $\frac{n_l}{(n_l+n_r+1)}$ or select root with probability $\frac{1}{n_l+n_r+1}$ or select $\frac{n_r}{n_l+n_r+1}$.
