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
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 leaves | distance $a$–$b$ | probability |
|---|---|---|---|
| $a$ itself | 1 | 0 | 1/8 |
| sibling of $a$ | 1 | 2 | 1/8 |
| other leaves under $a$'s grandparent | 2 | 4 | 2/8 |
| leaves in the other half of the tree | 4 | 6 | 4/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
- GATE 2018 CS Q28
- GATE 2018 CS Q53
- GATE 2015 CS (CS1) Q44
- GATE 2017 CS (CS1) Q30
- GATE 2014 CS (CS1) Q61
- GATE 2014 CS (CS1) Q62
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →