Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees

Source abstract

We study the variety of subtrees lying on the fringe of recursive trees and binary search trees by analyzing the distributional behavior of $X_{n,k}$, which counts the number of subtrees of size k in a random tree of size n, with $k = k(n)$ dependent on n. Using analytic methods we can characterize for both tree families the phase change behavior of $X_{n,k}$ as follows. In the subcritical case, when $k(n)/\sqrt{n} \to 0$, we show that $X_{n,k}$ is (after normalization) asymptotically normally distributed, whereas in the supercritical case, when $k(n)/\sqrt n \to \infty$, $X_{n,k}$ converges to 0. In the critical case, when $k(n) = \Theta(\sqrt{n}\,)$, we show that if $k/\sqrt{n}$ approaches a limit, then $X_{n,k}$ converges in distribution to a Poisson random variable, whereas if $k/\sqrt{n}$ does not approach a finite nonzero limit, the size oscillates and does not converge in distribution to any random variable. In regard to recursive trees and binary search trees, this provides an understanding of the complete spectrum of phases of $X_{n,k}$ and the gradual change from the subcritical to the supercritical phase.