# Expected distance between leaf nodes in a binary tree

Let T be a full binary tree with $$8$$ leaves. (A full binary tree has every level full). Suppose that 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 number of edges in the unique path between a and b) is ?

### My Attempt:

This question is really simple. The only thing I want to confirm is whether the answer to this question will be $$4.86$$ or $$4.25$$ ? As per me the answer should be $$4.86$$. I solved it this way: 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\times8$$. So, expectation $$= (34 \times 8)/(8 \times 7) = 4.86$$.

Am I correct with the answer?

• Your are unfair in calculating total path length (i.e. 34*8, means you assumed that all 8 leaf nodes has distance), then why are not counting as total number of ways (i.e., 8*8 instead of 8*7)? So, $$\frac{(34 \times 8)}{(8 \times 8)} = 4.25$$ Feb 19, 2019 at 8:18

Your answer assumes that once $$a$$ is chosen, there are $$7$$ possibilities for the $$b$$, at an average distance of $$34/7$$ (and this value doesn't depend on $$a$$). But this ignores the possibility that $$a$$ and $$b$$ are equal (distance $$0$$); since they are chosen independently this can happen, and so in fact there are $$8$$ possibilities for $$b$$ at an average distance of $$34/8$$.
Hint: Two leaf nodes can be selected in $$8\times8 = 64$$ ways.