The Distribution of Heights of Binary Trees and Other Simple Trees

The number, [formula omitted], of rooted plane binary trees of height ≤ h with n internal nodes is shown to satisfy [formula omitted] uniformly for δ⁻¹(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.