The Profile of Binary Search Trees

Abstract

We characterize the limiting behavior of the number of nodes in level $k$ of binary search trees $T_n$ in the central region $1.2 \log n \leq 2.8 \log n$. Especially we show that the width $\bar{V}_n$ (the maximal number of internal nodes at the same level) satisfies $\bar{V}_n \sim (n/\sqrt{4\pi\log n})$ as $n \to \infty$ a.s.