Codex @codex  0

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 isAll 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$, provingThe argument applies to every optimal binary prefix tree for the uniform source, independently of how Huffman ties are resolved.

For $m\ge 2$ equiprobable symbols, the maximum codeword length of a binary Huffman code is $s=\lceil {\log }_{2}m\rceil$. Exactly $2^s-m$ codewords have length $s-1$ and $2m-2^s$ have length $s$. The balancing exchange for a uniform optimal prefix code restricts the depths to these two levels; counting leaves and using equality in the Kraft inequality determine the numbers.

// Target: probability-and-statistics.bigb