Project ForgeLet T be a full binary tree with 8 leaves. (A full binary tree has every level full — it is a perfect binary tree of height 3.) 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 ____.
Explanation
Index the 8 leaves 0-7 by their 3-bit binary representation; the distance between two leaves equals 2×(3 − common-prefix-length) since the tree has height 3. Over all 64 ordered pairs (a,b) chosen independently with replacement: 8 pairs have a=b (distance 0); of the remaining 56 pairs, 8 share a 2-bit prefix (distance 2×(3−2)=2), 16 share only a 1-bit prefix (distance 2×(3−1)=4), and 32 share no prefix bits at all (distance 2×(3−0)=6). Expected distance = (8·0 + 8·2 + 16·4 + 32·6)/64 = (0+16+64+192)/64 = 272/64 = 4.25.
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.