TIGHT UPPER AND LOWER BOUNDS ON THE PATH-LENGTH OF BINARY-TREES

The external path length of a tree T is the sum of the lengths of the paths from the root to each external node. The maximal path length dif ference, DELTA, is the difference between the lengths of the longest a nd shortest such paths. Tight lower and upper bounds are proved on the external path length of binary trees with N external nodes and maxima l path length difference DELTA is prescribed. In particular, an upper bound is given that, for each value of DELTA, can be exactly achieved for infinitely many values of N. This improves on the previously known upper bound that could only be achieved up to a factor proportional t o N. An elementary proof of the known upper bound is also presented as a preliminary result. Moreover, a lower bound is proved that can be e xactly achieved for each value of N and DELTA less-than-or-equal-to N/ 2.