Maximal path length of binary trees. (English) Zbl 0821.68094

Summary: We further refine the bounds on the path length of binary trees of a given size by considering not only their sizes, but also their heights and fringe thicknesses (the difference between the length of their shortest root-to-leaf paths and their heights). We characterize the maximum-path-length binary trees of a given height, size and fringe thickness, and using this characterization, we give an algorithm to find the maximum-path-length binary trees of a given size and fringe thickness. The proof of the main result is based on two new tree transformations that preserve the height, size, and fringe thickness.


68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
Full Text: DOI


[1] Cameron, H., Extremal cost binary trees, Ph.D. Thesis (1991), University of Waterloo
[2] Cameron, H.; Wood, D., Pm numbers, ambiguity, and regularity, RAIRO informatique Théorique, 27, 261-275 (1993) · Zbl 0806.11007
[3] Cameron, H.; Wood, D., Binary trees, fringe thickness, and minimum path length (1993), unpublished manuscript
[4] De Santis, A.; Persiano, G., Tight upper and lower bounds on the path length of binary trees (1991), unpublished manuscript · Zbl 0767.05060
[5] Knuth, D. E., The Art of Computer Programming, Vol. 3: Sorting and Searching (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010
[6] Klein, R.; Wood, D., On the path length of binary tree, J. ACM, 36, 280-289 (1989) · Zbl 0674.68012
[7] Nievergelt, J.; Wong, C.-K., Upper bounds for the total path length of binary trees, J. ACM, 20, 1-6 (1973) · Zbl 0263.68022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.