Exploring binary trees and other simple trees

Philippe Flajolet, Andrew Odlyzko

Research output: Contribution to journalConference articlepeer-review

8 Scopus citations


The average height of a binary tree with n internal nodes is shown to be asymptotic to 2√πn. More generally the average height of a tree in a simple family s with n nodes is asymptotic to c(S)√πn where c(s) is a number (usually algebraic) which can be explicitly determined from S. These results are achieved by means of a detailed singularity analysis of corresponding generating functions,.

Original languageEnglish (US)
Article number4567821
Pages (from-to)207-216
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1980
Externally publishedYes
Event21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States
Duration: Oct 13 1980Oct 15 1980

Bibliographical note

Publisher Copyright:
© 1980 IEEE Computer Society. All rights reserved.


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

Cite this