<p>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$.</p>

<p>The probability that $w$ is the least common ancestor of the two nodes is the probability that:</p>

<blockquote>
  <p>(1) Both random nodes are in the subtree rooted at $w$;</p>
</blockquote>

<p>and we do <em>not</em> have that</p>

<blockquote>
  <p>(2) Both nodes are in $w$'s left subtree or both nodes are in $w$'s right subtree.</p>
</blockquote>

<p>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$.</p>

<p>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}] &amp;= \frac{\left(2^k-1\right)^2 - 2\left(2^{k-1}-1\right)^2}{\left(2^h - 1\right)^2} \\
&amp;=\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$.)</p>

<p>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}$.</p>

<p>The expected height is thus
\begin{align}
  &amp;\sum_{k=1}^h (k)\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2} \\
  &amp;\approx \sum_{k=1}^h \frac{(k)\left(2^{k-1} - 2^{-k}\right)}{2^h} \\
  &amp;\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.</p>

CC BY-SA 3.0
2013-10-20T23:50:14.170Z
What does Theta mean in the final formula? (A link to the wiki article, or even just the name would be fine)
John Smith
CC BY-SA 3.0
2013-10-21T00:35:27.693Z
http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations
Austin Buchanan
CC BY-SA 3.0
2013-10-21T02:21:55.813Z
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).
usul
CC BY-SA 3.0
2013-10-20T21:56:34.067Z
2013-10-20T21:56:34.067Z
usul
<p>We have a binary tree with height $h$, and for the sake of analysis assume it's a complete tree.</p>

<p>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?</p>

<p>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):</p>

<p>Tree height 1 (1 node), height of subtree: 1</p>

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

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

<p>What is the actual formula?</p>

<cc.complexity-theory><ds.algorithms>
Average height of the least common ancestor of 2 random nodes in a binary tree
John Smith
# Average height of the least common ancestor of 2 random nodes in a binary tree

(Asked by: username_0 on 2013-10-20)

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?

**Tags:** cc.complexity-theory, ds.algorithms

---

## 1 answers

### Answer by username_1 on 2013-10-20. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: What does Theta mean in the final formula? (A link to the wiki article, or even just the name would be fine)  
> **username_2**: http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations  
> **username_1**: 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).  

---

