The Distribution of Heights of Binary Trees and Other Simple Trees

Abstract

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