Exploring binary trees and other simple trees

Philippe Flajolet, Andrew Odlyzko

Research output: Contribution to journalConference articlepeer-review

7 Scopus citations

Abstract

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
DOIs
StatePublished - Jan 1 1980
Externally publishedYes
Event21st Annual Symposium on Foundations of Computer Science, FOCS 1980 - Syracuse, United States
Duration: Oct 13 1980Oct 15 1980

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

Cite this