Note on the heights of random recursive trees and random <i>m</i>‐ary search trees

Abstract

Abstract A process of growing a random recursive tree T n is studied. The sequence { T n } is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T n is asymptotic, with probability one, to c log n . In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ) −1 , where γ e 1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m ‐ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union‐find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley &amp; Sons, Inc.