The cost of a class of optimal binary trees

While algorithms exist which produce optimal binary trees, there are no direct formulas for the cost of such trees. In this note, we give a formula for the cost of the optimal binary tree built on m nodes with weights 1, 2, 3,…, m . The simplicity of this proof suggests that one can try to compute the cost of optimal trees for other special classes of weights.