## Randomly built binary search tree

Define a randomly built binary search tree on $n$ keys as one that arises from inserting the keys in random order into an initially empty tree, where each of the $n!$ permutations of the input keys is equally likely.

• Prove that the expected height of a randomly built binary search tree on $n$ distinct keys is $O({\log}n)$
Source: from book "Introduction to Algorithms"

0

0

0

0

0

0

0

0