Given a sequence of numbers a1, ..., aq, find a binary tree with q leaves minimizing max {h1 + a1, ..., hq + aq}, where hi is the distance from the ith leaf to the root, i = 1, ..., 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 a1, ..., 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.
