On the Optimality of Huffman Trees

Huffman’s well-known algorithm for the construction of optimal search trees is shown to have a more general optimality property than was previously known. A corollary of this general optimality property yields explicitly the optimal policy for the dynamic programming recurrence F( n ) = f( n ) + min 1 j n - 1 [ F( j ) + F( n - j ) ], where f is concave nondecreasing. Several one-dimensional search problems are described which give rise to this recurrence.