GATE CS 2019 Q.56 (CS Q.46): Binary Trees, Binary Search Trees and Balanced Trees

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) ________.

Your answer

Official answer and solution

Official answer: 4.25
From: Official GATE 2019 answer key

Solution

Enumerate the distance between any two leaves chosen uniformly and independently based on their lowest common ancestor level, and compute the expected value.

A full binary tree with 8 leaves has root at level 0, internal nodes at levels 1 and 2, and all $2^3 = 8$ leaves at level 3. The height of the tree is 3.

Two leaves $a$ and $b$ are chosen uniformly and independently at random from the 8 leaves. Thus, there are $8 \times 8 = 64$ equally likely pairs $(a, b)$ .

The distance between $a$ and $b$ is the number of edges on the unique path between them, which depends on their lowest common ancestor (LCA):

$a = b$ (same leaf): There are $8$ such pairs. The distance is $0$ .
LCA at level 2 (sibling leaves): Each leaf has $1$ sibling. There are $8 \times 1 = 8$ pairs. The path goes up 1 edge to the parent and down 1 edge to the sibling, giving distance $1 + 1 = 2$ .
LCA at level 1 (leaves sharing a grandparent but not a parent): Each leaf has $2$ such cousins in its subtree of size 4. There are $8 \times 2 = 16$ pairs. The path goes up 2 edges and down 2 edges, giving distance $2 + 2 = 4$ .
LCA at level 0 (root, leaves in different halves of the tree): Each leaf has $4$ leaves in the opposite half of the tree. There are $8 \times 4 = 32$ pairs. The path goes up 3 edges and down 3 edges, giving distance $3 + 3 = 6$ .

Verify the sum of pairs: $8 + 8 + 16 + 32 = 64$ pairs, which covers all possibilities.

The expected value of the distance is the weighted average:

E[D] = \frac{8 \times 0 + 8 \times 2 + 16 \times 4 + 32 \times 6}{64} = \frac{0 + 16 + 64 + 192}{64} = \frac{272}{64} = 4.25

Final answer

4.25

Common trap

Assuming $a$ and $b$ must be distinct leaves, giving 56 pairs and distance $(16 + 64 + 192)/56 = 272/56 \approx 4.86$ , but the question states they are chosen independently at random, allowing $a = b$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 56 of 65, printed as CS Q.46
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source