Tight bounds on the path length of binary trees

Abstract

The external path length of a tree T is the sum of the lengths of the paths from the root to the external nodes. The maximal path length difference Δ is the difference of the lengths of the longest and shortest such path.

The external path length of binary trees with a given maximal path length difference Δ and given number of external nodes N has been studied by Klein and Wood. Namely, they have given upper bounds by using some results in [5] concerning properties of the ratio of the geometric and the harmonic means of integers (see [1]) and Lagrange multipliers (see [2]).

In this paper, we develop a new and very simple technique to obtain upper bounds. This allows us to present a simple derivation of their upper bound and successively improve their result. Namely, we derive a more precise upper bound that is also tight for every Δ and infinitely many N. We also manage to characterize for each N the tree with longest path length and Δ=2 and thus derive a matching upper bound for the case Δ=2; i.e. a bound that is achieved for all N. Finally, we initiate the study of lower bounds by presenting a matching lower bound for the case Δ=2.

Part of this work was done while the author was visiting IBM Research Division, T. J. Watson Research Ctr, Yorktown Heights, NY 10598.

Partially supported by ONR Grant # N00039-88-C-0613