Profile of random recursive trees and random binary search trees

We give new results on the profile (the number of nodes at each level) of random recursive trees and random binary search trees. The profile of random recursive trees converges in distribution to some non-normal law when the limit ratio $\alpha$ of the level and the logarithmic tree size lies in the interval $[0,e)$; convergence of all moments is shown to hold only for $\alpha\in[0,1]$, outside the unit interval only convergence of finite moments being possible. When the limit ratio is 0 or 1, the profile (properly centered and normalized) is shown to be asymptotically normally distributed when $\alpha=0$ and to converge to a ``quicksort type" limit law when $\alpha=1$. The tools used are based on method of moments and contraction method. Similar phenomena also hold for other classes of random trees with logarithmic height like binary search trees, m-ary search trees, quadtrees, median-of-$(2t+1)$ binary search trees, etc. The profiles of these random trees represent concrete examples for which the range of convergence in distribution and that of convergence of all moments differ. Other new features of such trees like bimodality of the variance are also presented.

This talk is based on joint work with Michael Drmota, Michael Fuchs, and Ralph Neininger.