GATE 2019 CS – Question 56
Let $T$ be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves $a$ and $b$ of $T$ are chosen uniformly and independently at random. The expected value of the distance between $a$ and $b$ in $T$ (i.e., the number of edges in the unique path between $a$ and $b$) is (rounded off to 2 decimal places) ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4.23 to 4.27
Explanation
For a fixed $a$, the leaf $b$ is $a$ itself (prob $\frac18$, distance 0), its sibling (prob $\frac18$, distance 2), one of the 2 other leaves under the grandparent (prob $\frac28$, distance 4) or one of the 4 leaves on the other side (prob $\frac48$, distance 6). So $E=\frac{0+2+8+24}{8}=4.25$.