Optimal binary trees with order constraints

Given a sequence of numbers a(1),...,a(q), find a binary tree with q leaves minimizing max{h(1) + a(1),...,h(q) + a(q)}, where h(i) is the distance fr om the ith leaf to the root, i = 1,...,q. This problem is solved by means o f a O(q) algorithm and a tight upper bound for the minimum is given by an e xplicit formula, The task is equivalent to finding a binary tree of minimum height having q subtrees of heights a(1),...,a(q) whose leaves partition t he leaves of the tree. This question seems to be of general interest. In pa rticular, it arises in the problem of the optimal decomposition of a tree i nto chains (Waksman, Tech. Report FC 95-06, August 1995). (C) 1999 Elsevier Science B.V. All rights reserved.