= Solution
A <full binary tree> has Kraft sum one. For example, place mass one at the root and divide each internal vertex's mass equally between its children; a leaf at depth $l$ receives $2^{-l}$, and the total mass on leaves remains one. Using part d gives the two equations
$$
n_{s-1}+n_s=m,\qquad \frac{n_{s-1}}{2^{s-1}}+\frac{n_s}{2^s}=1.
$$
Multiplying the second equation by $2^s$ and subtracting the first gives the <uniform-source Huffman length distribution>
$$
\boxed{n_{s-1}=2^s-m,\qquad n_s=2m-2^s,\qquad s=\lceil\log_2m\rceil.}
$$
If $m=2^s$, the first number is zero and every <codeword> has length $s$. Otherwise both levels occur. The corresponding mean length is $L=s-(2^s-m)/m$.
Back to article page
