Binary Trees Optimum Under Various Criteria
T. C. Hu, Daniel J. Kleitman, Jeanne K. Tamaki · SIAM Journal on Applied Mathematics · 1979
In this paper we construct binary trees optimal under various criteria. In particular, we show that Hu–Tucker type algorithms can be used to find trees, whose leaves preserve a given order, that minimize certain sums of functions of path length, and also that minimize certain maximum functions of path length. The arguments are based on a new proof of the original Hu–Tucker algorithm.