Tight upper and lower bounds on the path length of binary trees. (English) Zbl 0802.68034

Summary: 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 difference, \(\Delta\), is the difference between the lengths of the longest and shortest such paths.
Tight lower and upper bounds are proved on the external path length of binary trees with \(N\) external nodes and maximal 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 to \(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 exactly achieved for each value of \(N\) and \(\Delta \leq N/2\).


68P05 Data structures
68P10 Searching and sorting
05C35 Extremal problems in graph theory
05C05 Trees
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI