The average height of binary trees and other simple trees

Philippe Flajolet, Andrew Odlyzko

Research output: Contribution to journalArticlepeer-review

158 Scopus citations

Abstract

The average height of a binary tree with n internal nodes is shown to be asymptotic to 2√πn. This represents the average stack height of the simplest recursive tree traversal algorithm. The method used in this estimation is also applicable to the analysis of traversal algorithms of unary-binary trees, unbalanced 2-3 trees, t-ary trees for any t, and other families of trees. It yields the two previously known estimates about average heights of trees, namely for labeled nonplanar trees (a result due to Renyi and Szekeres) and for planar trees (a result of De Bruijn, Knuth, and Rice). The method developed here, which relies on a singularity analysis of generating functions, is new and widely applicable.

Original languageEnglish (US)
Pages (from-to)171-213
Number of pages43
JournalJournal of Computer and System Sciences
Volume25
Issue number2
DOIs
StatePublished - Oct 1982
Externally publishedYes

Fingerprint

Dive into the research topics of 'The average height of binary trees and other simple trees'. Together they form a unique fingerprint.

Cite this