Let π be a full binary tree with 8 leaves. (A full binary tree has everyβ¦
2019
Let π be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves π and π of π are chosen uniformly and independently at random. The expected value of the distance between π and π in π (i.e., the number of edges in the unique path between π and π) is (rounded off to 2 decimal places) .
Attempted by 122 students.
Show answer & explanation
Correct answer: 4.25
Key facts: the tree is a perfect binary tree with 8 leaves, so its height is 3 and every leaf is at depth 3.
If the lowest common ancestor (LCA) of the two leaves is at depth d, the distance between the leaves is 6 - 2d (because each leaf is at depth 3).
Compute probabilities for the LCA depth when two leaves are chosen independently and uniformly (so the same leaf may be chosen twice):
P(LCA depth = 0) = 1/2; P(LCA depth = 1) = 1/4; P(LCA depth = 2) = 1/8; P(LCA depth = 3) = 1/8.
Now take the expectation of the distance:
E(distance) = 6*(1/2) + 4*(1/4) + 2*(1/8) + 0*(1/8) = 3 + 1 + 0.25 + 0 = 4.25.
Rounded to two decimal places the expected distance is 4.25.
A video solution is available for this question β log in and enroll to watch it.