GATE CS 2019 Q46 — Trees

A full binary tree (where every level is completely filled) with $8$ leaves has a height of $3$. Let the root be at depth $0$, and the $8$ leaves be at depth $3$.

Since two leaves $a$ and $b$ are chosen uniformly and independently at random, there are $8 \times 8 = 64$ possible ordered pairs $(a, b)$. The distance $d(a, b)$ between any two leaves depends on the depth of their Lowest Common Ancestor (LCA):

• Case 1: $a = b$ (LCA at depth 3)
  The distance is $0$. There are $8$ such pairs.
• Case 2: $a$ and $b$ are siblings (LCA at depth 2)
  The distance is $2 + 2 - 2(2) = 2$. For each leaf, there is exactly $1$ sibling. There are $8 \times 1 = 8$ such pairs.
• Case 3: LCA is at depth 1
  The distance is $3 + 3 - 2(1) = 4$. For each leaf, there are $2$ such leaves in the adjacent sibling subtree. There are $8 \times 2 = 16$ such pairs.
• Case 4: LCA is the root (depth 0)
  The distance is $3 + 3 - 2(0) = 6$. For each leaf, there are $4$ such leaves in the opposite half of the tree. There are $8 \times 4 = 32$ such pairs.

We can verify the total number of pairs: $8 + 8 + 16 + 32 = 64$.

The expected value of the distance is: