Distribution of distances in random binary search trees.
The authors prove asymptotic normality for the depth of a randomly selected node and for the distance between two randomly selected nodes in a random binary search tree. They also establish logarithmic convergence rates w.r.t. the Zolotarev metric. The proof is based on the contraction method.
scientific article; zbMATH DE number 1906137
scientific article