Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees

We consider sums of functions of subtrees of a random binary search tree and obtain general laws of large numbers and central limit theorems. These sums correspond to random recurrences of the quicksort type, Xₙ L= XIₙ + X'n-1-Iₙ + Yₙ, n ≥ 1, where In is uniformly distributed on {0,1,. . ., n-1 }, Yn is a given random variable, Xₖ L= X'ₖ for all k, and, given In, XIn and X'n-1-In are independent. Conditions are derived such that (Xₙ - μ n )/σ √n L→ N(0,1), the normal distribution, for some finite constants μ and σ.