GATE CS 2019 Set 1 — Question 56

Given that $T$ is a full binary tree (perfect binary tree) with 8 leaves, we can determine its height $h$.
For a perfect binary tree, the number of leaves is $2^h$. Thus, $2^h = 8 \implies h = 3$.
The tree has levels $0, 1, 2, 3$, where the root is at level 0 and leaves are at level 3.We choose two leaves $a$ and $b$ uniformly and independently at random. Since there are 8 leaves, the total number of possible pairs $(a, b)$ is $8 \times 8 = 64$.The distance between two nodes in a tree is the number of edges on the unique path between them. For two leaves $a$ and $b$ at depth $h$, the distance is given by:$$dist(a, b) = depth(a) + depth(b) - 2 \times depth(LCA(a, b))$$$$dist(a, b) = 3 + 3 - 2 \times depth(LCA(a, b)) = 6 - 2 \times depth(LCA(a, b))$$where $LCA(a, b)$ is the Lowest Common Ancestor of $a$ and $b$.We analyze the possible depths of the LCA: The root has a left subtree and a right subtree. Each subtree contains $2^{3-1} = 4$ leaves.
The LCA is the root if $a$ is in the left subtree and $b$ is in the right subtree, or vice versa.
Number of pairs = $(4 \times 4) + (4 \times 4) = 16 + 16 = 32$.
Distance = $6 - 2(0) = 6$.
Contribution to sum = $32 \times 6 = 192$. There are $2^1 = 2$ nodes at depth 1. Each is the root of a subtree with height 2 (leaves at relative depth 2).
Each node at depth 1 has a left child and a right child, each leading to $2^{2-1} = 2$ leaves.
For a specific node at depth 1 to be the LCA, one leaf must be in its left branch (2 choices) and the other in its right branch (2 choices), or vice versa.
Pairs per node = $(2 \times 2) + (2 \times 2) = 8$.
Total pairs for 2 nodes = $2 \times 8 = 16$.
Distance = $6 - 2(1) = 4$.
Contribution to sum = $16 \times 4 = 64$. There are $2^2 = 4$ nodes at depth 2. Each has 2 leaves as children (1 left, 1 right).
For a node at depth 2 to be the LCA, one leaf must be left (1 choice) and the other right (1 choice), or vice versa.
Pairs per node = $(1 \times 1) + (1 \times 1) = 2$.
Total pairs for 4 nodes = $4 \times 2 = 8$.
Distance = $6 - 2(2) = 2$.
Contribution to sum = $8 \times 2 = 16$. This occurs when $a = b$. There are 8 leaves.
Total pairs = 8.
Distance = $6 - 2(3) = 0$.
Contribution to sum = 0.Total Sum of Distances:$$Sum = 192 + 64 + 16 + 0 = 272$$Expected Distance:$$E[dist] = \frac{\text{Total Sum}}{\text{Total Pairs}} = \frac{272}{64}$$$$E[dist] = \frac{136}{32} = \frac{68}{16} = \frac{17}{4} = 4.25$$The expected value is 4.25.