Spanning tree size in Random Binary Search Trees

Alois Panholzer, Helmut Prodinger

This paper deals with the size of the spanning tree of p randomly chosen nodes in a binary search tree. It is shown via generating functions methods, that for fixed p, the (normali…