Past exam of the communication Theory course of the University of Oxford / 2009 / 2 / b / 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 equality, ${\sum }_x{2}^{-{\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^n{2}^{-n}=1$, a contradiction. Since the code is not a block code, the alternative that all lengths equal $n$ is excluded. Therefore 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.