The GATE Grind

GATE 2019 CS – Question 56

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Numerical answer

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

A full binary tree with 8 leaves has depth 3. Fix leaf $a$ and look at where a uniformly random leaf $b$ can be:

$b$number of leavesdistance $a$–$b$probability
$a$ itself101/8
sibling of $a$121/8
other leaves under $a$'s grandparent242/8
leaves in the other half of the tree464/8

$$E=\frac{1\cdot0+1\cdot2+2\cdot4+4\cdot6}{8}=\frac{0+2+8+24}{8}=\frac{34}{8}=\mathbf{4.25}.$$

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →