The Distribution of Heights of Binary Trees and Other Simple Trees

Philippe Flajolet, Zhicheng Gao, Andrew Odlyzko, Bruce Richmond

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

The number, [formula omitted], of rooted plane binary trees of height ≤ h with n internal nodes is shown to satisfy [formula omitted] uniformly for δ−1(log n)−1/2 ≤ β ≤ δ(log n)1/2, where [formula omitted] and δ is a positive constant. An asymptotic formula for [formula omitted] is derived for h = cn, where 0 < c < 1. Bounds for [formula omitted] are also derived for large and small heights. The methods apply to any simple family of trees, and the general asymptotic results are stated.

Original languageEnglish (US)
Pages (from-to)145-156
Number of pages12
JournalCombinatorics, Probability and Computing
Volume2
Issue number2
DOIs
StatePublished - Jun 1993

Fingerprint Dive into the research topics of 'The Distribution of Heights of Binary Trees and Other Simple Trees'. Together they form a unique fingerprint.

Cite this