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.

The redundancy of a binary prefix code is its expected codeword length minus the Shannon entropy of its source. It measures the excess number of binary digits per source symbol above the information lower bound. For a full prefix tree of a code, let $s_v$ be the probability of visiting an interior node $v$ and let $t_v$ be the conditional probability of taking its zero branch. Thenwhere $h$ is binary entropy. The first identity counts one digit for each visited interior node. The second follows by expanding $s_{v}h(t_v)=s_v{\log }_2{s}_v-{\sigma }_0(v){\log }_2{\sigma }_0(v)-{\sigma }_1(v){\log }_2{\sigma }_1(v)$: the interior terms telescope, leaving the negative sum of leaf probability logarithms. The final identity follows by subtraction. It makes nonnegativity immediate and proves that zero redundancy occurs exactly when each positive-mass branch decision is balanced. Consequently the leaf probabilities then equal $2^{-{\ell }_x}$.