= Solution
Every internal node of an optimal binary prefix tree has two children. If one had only one child, remove that one-edge detour from all descendant words. Prefix-freeness is preserved and at least one positive-<probability> word becomes shorter, strictly lowering the expected length. Thus the tree is full.
Take a leaf at maximum depth $L$. Its sibling exists because the tree is full. That sibling cannot be an internal node, since a descendant would be deeper than $L$. Hence it is another leaf at depth $L$, and the corresponding codewords differ only in their final bit. This is the <deepest sibling property of an optimal prefix code>.
A finite full binary tree satisfies <Kraft inequality>[Kraft equality], $\sum_x2^{-\ell_x}=1$, by dividing mass equally down each branch from the root. If all $2^n$ lengths were at least $n$, with at least one strictly greater, that sum would be less than $2^n2^{-n}=1$, a contradiction. Since the code is not a <block code>, the alternative that all lengths equal $n$ is excluded. Therefore \b[some word has length below $n$]. Also a longest word must have length above $n$: if all lengths were at most $n$ and some shorter, the Kraft sum would exceed one.
Back to article page
