Tight bounds on the path length of binary trees. (English) Zbl 0767.05060

Theoretical aspects of computer science, Proc. 8th Annu. Symp., STACS ’91, Hamburg/Ger. 1991, Lect. Notes Comput. Sci. 480, 478-487 (1991).
Summary: [For the entire collection see Zbl 0753.00019.]
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 \(\Delta\) 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 \(\Delta\) and given number of external nodes \(N\) has been studied by R. Klein and D. Wood. Namely, they have given upper bounds by using some results in W. Specht [Math. Z. 74, 91-98 (1960; Zbl 0095.038)] concerning properties of the ratio of the geometric and the harmonic means of integers (see R. Klein and D. Wood [J. Assoc. Comp. Mach. 36, No. 2, 280-289 (1989; Zbl 0674.68012)]) and Lagrange multipliers.
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 \(\Delta\) and infinitely many \(N\). We also manage to characterize for each \(N\) the tree with longest path length and \(\Delta=2\) and thus derive a matching upper bound for the case \(\Delta=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 \(\Delta=2\).


05C35 Extremal problems in graph theory
05C05 Trees
05C38 Paths and cycles