1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 6 '16 at 7:43
  • $\begingroup$ Also, when you say on average, you have to explain how a random binary search tree is constructed. $\endgroup$ – Yuval Filmus Mar 6 '16 at 7:47
4
$\begingroup$

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)$.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Your link claims the average depth of a uniform random binary search tree is sqrt(n), which sounds about right to me since a uniform random binary search tree is unlikely to be perfectly balanced. Did you mean a balanced BST? $\endgroup$ – Kevin Mar 6 '16 at 8:41
  • $\begingroup$ I have corrected the answer. $\endgroup$ – Shreesh Mar 6 '16 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.