Optimal binary trees with order constraints (Q1283811)

An \(O(q)\)-algorithm is designed for the following problem: given a sequence of numbers \(a_1,\dots, a_q\), construct a binary tree with \(q\) leaves minimizing \(\max\{h_1+ a_1,\dots, h_q+ a_q\}\), where \(h_i\) is the distance from the \(i\)th leaf to the root, \(i= 1,\dots, q\). A sharp upper bound for the minimum is given by an explicit formula.