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$$.

MSC:

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