1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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$$ $\endgroup$ – ً ً Feb 19 '19 at 8:18
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Hint: Two leaf nodes can be selected in $8\times8 = 64$ ways.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.