# Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average

I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it $\mathcal{O}(n)$:

depth(tree):
if tree is a leaf:
return 0
else:
return 1 + max(depth(tree.left_subtree), depth(tree.right_subtree))


It goes through each and every node. Could someone explain to me how finding the depth of a BST can be done is $\mathcal{O}(\log n)$ on average?

• They want you to prove that the depth of a binary search tree is $O(\log n)$ on average, not that it takes $O(\log n)$ to calculate it using the recursive procedure you give. – Yuval Filmus Mar 6 '16 at 7:43
• Also, when you say on average, you have to explain how a random binary search tree is constructed. – Yuval Filmus Mar 6 '16 at 7:47

If your input binary search tree is like the one given below then no matter what the program does, the depth function will return $n-1$ (because the depth is $n-1$, in this case). And it will take $n$ operations if the program does not know the depth beforehand or by some trickery, or the depth is not stored, say, in nodes.
(1) depth function returns $d$, the depth of the tree, which is fixed for a given tree.
(2) depth function the way it is defined will always run in $O(n)$ time for any tree, skewed or balanced.
(3) the average depth $E(d)$ of a random binary search tree (which is got by randomly inserting $n$ uniform random values) is $O(\log n)$.