**This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.**

### Abstract

This entry contains proofs for the textbook results about the distributions of the height and internal path length of random binary search trees (BSTs), i. e. BSTs that are formed by taking an empty BST and inserting elements from a fixed set in random order.

In particular, we prove a logarithmic upper
bound on the expected height and the *Θ(n log n)*
closed-form solution for the expected internal path length in terms of
the harmonic numbers. We also show how the internal path length
relates to the average-case cost of a lookup in a BST.