Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) 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 (rounded off to 2 decimal places).

Full binary tree with 8 leaves:

Since any two leaves is chosen uniformly and independently at random

Possible distance: 0, 2, 4, and 6

Leaves with 0 distance:

{(p, p), (q, q), (r, r), (s, s), (t, t), (u, u), (v, v), (w, w)}

 Leaves with 2 distance:

{(p, q), (q, p), (r, s), (s, r), (t, u), (u, t), (v, w), (w, v)}

Leaves with 4 distance:

{(p, r), (r, p), (p, s), (s, p), (q, r), (r, q), (q, s), (s, q),

(t, v), (v, t), (t, w), (w, t), (u, v), (v, u), (u, w), (w, u),}

Leaves with 6 distance:

{(p, t), (t, p), (p, u), (u, p), (p, v), (v, p), (p, w), (w, p),

(q, t), (t, q), (q, u), (u, q), (q, v), (v, q), (q, w), (w, q),

(r, t), (t, r), (r, u), (u, r), (r, v), (v, r), (r, w), (w, r),

(s, t), (t, s), (s, u), (u, s), (s, v), (v, s), (s, w), (w, s)}

Total nodes possible with 0, 2, 4, and 6 distance is 64.

\(E\left( {{x_i}} \right) = \mathop \sum \limits_{i = 1}^4 {x_i}{p_i}\)

\(E\left( {{x_i}} \right) = 0 \times \frac{8}{{64}} + 2 \times \frac{8}{{64}} + 4 \times \frac{{16}}{{64}} + 6 \times \frac{{32}}{{64}}\)

\(E\left( {{x_i}} \right) = \frac{1}{4} + 1 + 3 = 4.25\)