From Philippe.Flajolet@inria.fr Fri Jul 25 14:22:30 1997
Date: Fri, 25 Jul 1997 14:22:28 +0200
Subject: AofA (answer to Q1)

I hope I'm not mistaken.

The depth of the minimum or maximum in a random binary search tree (BST)
of size $n$ has a Stirling cycle distribution, as is
well known. (See, eg, Sedewick-Flajolet, Analysis of Algorithms):
The probability distribution of a min or max is
$$s_n(x)=\frac{\Gamma(x+n)}{\Gamma(n)}=x(x+1)\cdots(x+n-1).$$
(Depth is measured by number of nodes on the branch.)

Now, the element $j$ in a random BST of size $n$ is at the same time
the maximum of the subpermutation induced by$[1..j]$ and the minimum
of the subpermutation induced by $[j..n]$. Both subpermutations are random.
Thus, the probability generating function (PGF) of element $j$ in 
a random BST of size $n$ is
$$S_{n,j}=\frac{1}{x}s_j(x)s_{n+1-j}(x),$$
where we "avoid" to count the root twice.

This has the following easy consequences:
$(i)$ the mean depth of $j$ is $H_j+H_{n+1-j}-1$ [well known];
$(ii)$ the variance is similarly deducible from the variance of min or
        max [also known];
$(iii)$ the exact distribution is expressed by a single convolution of
        Stirling cycle numbers;
$(iv)$ as $n\to\infty$, the asymptotic distribution is Gaussian, for
instance, when $j$ is fixed or in the quantile case $j=\alpha n$ [by a mild
extension of Goncharov's famous 1944 theorem on Stirling cycle numbers]