Optimal Binary Search Trees with Restricted Maximal Depth
Michael R. Garey · SIAM Journal on Computing · 1974
An algorithm is given for constructing a binary tree of minimum weighted path length for n nonnegative weights under the constraint that no path length exceed a given bound L. The number of operations required is proportional to $Ln^2 $. Such problems, which impose an additional constraint on the usual Huffman tree, arise in many applications, including computer file searching and the construction of optimal prefix codes under certain practical conditions.