Path Length of Binary Search Trees
T. C. Hu, Kay Chen Tan · SIAM Journal on Applied Mathematics · 1972
An algorithm is given for constructing a binary tree of minimum weighted path length and with restricted maximum path length. (Huffman’s tree is a binary tree of minimum weighted path length with no restriction on maximum path length.) When an alphabetical ordering of the terminal nodes is introduced, the binary tree is called an alphabetic binary tree. We show that Huffman’s algorithm for optimal binary trees coincides with the T-C algorithm for optimal alphabetic binary trees when the terminal nodes have monotonically increasing weights from left to right.