= Solution
Suppose a leaf has depth $t\le s-2$. By part a there is a sibling pair of leaves at depth $s$. These leaves are disjoint from the shallow leaf and its descendants, since a leaf has no descendants. Modify the <prefix tree of a code> by splitting the shallow leaf into two leaves at depth $t+1$ and replacing the deepest sibling pair by their parent as one leaf at depth $s-1$. The number of leaves remains $m$, so assign the equiprobable source letters bijectively to the new leaves.
The sum of depths for the three affected leaves changes from $t+2s$ to $2(t+1)+(s-1)$. The change is
$$
2(t+1)+(s-1)-(t+2s)=t-s+1\le-1.
$$
All other depths are unchanged. Since probabilities are equal, this strictly decreases the <expected codeword length>, contradicting the optimality of the <Huffman code>. This is the <balancing exchange for a uniform optimal prefix code>. There is therefore no leaf of depth at most $s-2$, proving
$$
\boxed{s_i\in\{s-1,s\}\text{ for every }i,\qquad n_{s-1}+n_s=m.}
$$
The argument applies to every optimal binary prefix tree for the uniform source, independently of how Huffman ties are resolved.
Back to article page
