6
$\begingroup$

We have a binary tree with height $h$, and for the sake of analysis assume it's a complete tree.

If we pick two nodes at random (with or without replacement, your choice), what is the expected height of the subtree rooted at the least common ancestor of those nodes?

I believe I've calculated the first few results, by exhaustive case analysis (for the situation of choosing a node at random with replacement, i.e. both nodes may be the same):

Tree height 1 (1 node), height of subtree: 1

Tree height 2 (3 nodes), height of subtree: 1.666... (5/3)

Tree height 3 (7 nodes), height of subtree: 2.551... (125/49)

What is the actual formula?

$\endgroup$
2
$\begingroup$

It took me a while to see the nice formula, but there is one. Consider a node $w$ at height $k$. The root is at height $h$ and the leaves at height $1$.

The probability that $w$ is the least common ancestor of the two nodes is the probability that:

(1) Both random nodes are in the subtree rooted at $w$;

and we do not have that

(2) Both nodes are in $w$'s left subtree or both nodes are in $w$'s right subtree.

The size of a subtree at height $k$ is $2^k-1$. The probability of #1 is therefore $\left(\frac{2^k-1}{2^h - 1}\right)^2$. The probability of #2 is $2 \left(\frac{2^{k-1}-1}{2^h - 1}\right)^2$.

The probability of the event that #1 happens and #2 does not (since #2 is a subset of #1) is thus \begin{align} \Pr[\text{$w$ at height $k$ is lca}] &= \frac{\left(2^k-1\right)^2 - 2\left(2^{k-1}-1\right)^2}{\left(2^h - 1\right)^2} \\ &=\frac{2^{2k-1} - 1}{\left(2^h -1 \right)^2} \end{align} once you work it out. (You can check that these probabilities sum to $1$.)

There are $2^{h-k}$ nodes at height $k$. So the probability that the lca is at height $k$ is $\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2}$.

The expected height is thus \begin{align} &\sum_{k=1}^h (k)\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2} \\ &\approx \sum_{k=1}^h \frac{(k)\left(2^{k-1} - 2^{-k}\right)}{2^h} \\ &\approx h - 1 - \Theta\left(\frac{1}{2^h}\right) . \end{align} Simulations bear this out up to three decimal points anyway. By the way, this is very easy to simulate: Suppose the nodes are numbered $1,2,\dots, 2^h - 1$. Pick two random numbers from this range. Now each node $x$'s parent is $\lfloor \frac{x}{2} \rfloor$. To find the lca of two numbers, continue halving (and rounding down) the larger number until they are equal. To find the height of a number, continue halving (and rounding down) until it is one and count the steps. So if your random number generator is comfortable giving you random numbers in the range $[1,2^{100}]$ (as python's seems to be) then you can simulate easily.

$\endgroup$
  • $\begingroup$ What does Theta mean in the final formula? (A link to the wiki article, or even just the name would be fine) $\endgroup$ – John Smith Oct 20 '13 at 23:50
  • $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Austin Buchanan Oct 21 '13 at 0:35
  • $\begingroup$ Yep, as Austin said. The point being that for $h$ very big at all, the $h-1$ is all that matters (other terms are tiny). $\endgroup$ – usul Oct 21 '13 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.