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

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

Solution:

Sum of distances from a particular leaf to the remaining 7 leaves is 34. The sum would remain the same for each leaf node. Therefore total sum of distance of all the leaf nodes = 34*8.

Two leaf nodes can be selected in 8*8 = 64 ways.

Therefore, the expected value of the length between a and b in T,

= (34*8) / (8*8)

= 34 / 8

= 4.25