From conrado@lsi.upc.es Tue Jul 22 15:40:32 1997
From: Conrado Martinez Parra <conrado@lsi.upc.es>
Date: Tue, 22 Jul 1997 15:40:27 +0200 (MET DST)

Open Problem:

Let $D_{n,j}$ denote the depth of the $j$-th internal node in a random
binary search tree of size $n$. We assume that the internal nodes are
labelled $1..n$ follwoing the inorder traversal of the tree, as usual.
Which is the probability that $D_{n,j}=k$? A slightly easier problem
(but also very interesting) would be to study the limiting
probability distribution of $D_{n,\alpha n}$ as $n\to\infty$ and fixed
$\alpha$, $0<\alpha < 1$, if such limiting distribution exists.