Optimal binary trees with order constraints

Given a sequence of numbers al, …, aq, find a binary tree with q leaves minimizing max hl + al, …, hq + aq, where hi is the distance from the ith leaf to the root, i = l, …, q. This problem is solved by means of a O(q) algorithm and a tight upper bound for the minimum is given by an explicit formula. The task is equivalent to finding a binary tree of minimum height having q subtrees of heights al, …, aq whose leaves partition the leaves of the tree. This question seems to be of general interest. In particular, it arises in the problem of the optimal decomposition of a tree into chains (Waksman, Tech. Report FC 95-06, August 1995).