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?