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

Question

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?

Answer 1

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.

You are confusing three things in your question:
(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)$.