Binary trees, fringe thickness and minimum path length. (English) Zbl 0833.68092

Summary: We solve the following problem: Characterize the minimum-path-length binary trees with respect to size and fringe thickness, where the fringe thickness of a tree is the difference between the lengths of shortest and longest root-to-frontier paths. This result demonstrates that minimum path length is, in this setting, more amenable to analysis than maximum path length.


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


[1] . H. CAMERON, Extremal Cost Binary Trees, PhD thesis, University of Waterloo, 1991.
[2] . H. CAMERON and D. WOOD, Maximal path length of binary trees, Discrete Applied Mathematics, 1994, 55 (1), pp. 15-35. Zbl0821.68094 MR1298512 · Zbl 0821.68094
[3] . R. DE PRISCO, G. PARLATI and G. PERSIANO, On the path length of trees with known fringe, Unpublished manuscript, 1994. · Zbl 0875.68705
[4] . A. DE SANTIS and G. PERSIANO, Tight upper and lower bounds on the path length of binary trees, SIAM Journal on Computing, 1994, 23 (1), pp. 12-23. Zbl0802.68034 MR1258991 · Zbl 0802.68034
[5] . D. E. KNUTH, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, MA, 1973. MR445948 · Zbl 0191.17903
[6] . R. KLEIN and D. WOOD, On the path length of binary trees, Journal of the ACM, 1989, 36 (2), pp. 280-289. Zbl0674.68012 MR1072422 · Zbl 0674.68012
[7] . J. NIEVERGELT and CHAK-KUEN WONG, Upper bounds for the total path length of binary trees, Journal of the ACM, January 1973, 20 (1), pp. 1-6. Zbl0263.68022 MR495300 · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.