= Solution
If all leaves of a <full binary tree> have depth $s$, all binary paths of length $s$ end in leaves. Thus it has exactly $2^s$ leaves and $m=2^s$. Equivalently, equality in the <Kraft inequality> gives $m2^{-s}=1$.
Conversely, when $m=2^k$ a complete depth-$k$ tree is a <prefix code> with mean length $k$. For any prefix lengths $s_i$, convexity gives
$$
2^{-L}\le\frac1m\sum_{i=1}^m2^{-s_i}\le\frac1m,\qquad L=\frac1m\sum_i s_i,
$$
so $L\ge\log_2m=k$. The complete tree is optimal. A <Huffman code> attains this optimum, and equality in the strictly convex first inequality forces all its lengths to equal $k$. Hence, for $m\ge2$,
$$
\boxed{n_s=m\quad\Longleftrightarrow\quad m\text{ is a power of two}.}
$$
This also proves that ties in the Huffman construction do not change the conclusion.
Back to article page
