= Solution
Use the balancing fact proved by the exchange argument in part d: every leaf of an optimal tree has depth $s-1$ or $s$. A <full binary tree> with this property has all $2^{s-1}$ possible vertices at level $s-1$; at least one of these is split into two deepest leaves. Thus
$$
2^{s-1}<m\le2^s.
$$
These inequalities characterize the maximum <codeword length> exactly:
$$
\boxed{s=\lceil\log_2m\rceil.}
$$
In the suggested notation $m=a2^k$, $1\le a<2$, this is $s=k$ for $a=1$ and $s=k+1$ for $1<a<2$. The distinction at a power of two is important.
Back to article page
