4
$\begingroup$

Below is a question I was asked in an Interview

What is the best case time complexity to find the height of a Binary Search Tree?

I answered it explaining using the below algorithm

$\mathrm{height}(v)$

if $v$ is a leaf, return 0

otherwise, return $\max(\mathrm{height}(v.\mathit{left}), \mathrm{height}(v.\mathit{right})) + 1$

So, in best case, my recurrence would become

$$T(n)=2T\left(\frac{n}{2}\right) + c.$$

Here $T(\frac{n}{2})$ is for each of the recursive calls, and $c$ for all the rest. So even best case complexity is $O(n)$.

Now, in the worst case, my recurrence would become

$$T(n)=T(n-1)+c,$$

and this would be a case of a skewed BST. Still, here complexity remains $O(n)$.

So, in all cases, the time complexity to find the height of a BST remains $O(n)$.

Is my claim correct?

$\endgroup$
  • $\begingroup$ The skewed case is the worst case scenario, and this will be enough for calculating the Big-Oh of the problem. So $O(n)$ is indeed the correct claim. $\endgroup$ – Sagnik Jul 30 '18 at 5:57
  • $\begingroup$ @Sagnik-And the best case would also be $\Omega(n)$, right? $\endgroup$ – user3767495 Jul 30 '18 at 7:15
5
$\begingroup$

Your algorithm runs in linear time on all inputs. The algorithm visits each node of the tree exactly once, and does $O(1)$ work per node. Therefore it runs in time $\Theta(n)$, where $n$ is the number of nodes.

The argument above is better than using recurrences, since it is more immediate. It also shows that if you had an arbitrary tree (not necessarily binary), the algorithm would still run in linear time.

$\endgroup$
  • $\begingroup$ More of an aggregate analysis...am i correct @YuvalFilums ? $\endgroup$ – Navjot Waraich Jul 30 '18 at 8:06
  • $\begingroup$ I'm not familiar with this term. $\endgroup$ – Yuval Filmus Jul 30 '18 at 8:27
0
$\begingroup$

I think that best time complexity is O(sqrt(N)) if BST doesn't contain duplicates. The point is that subtree may be limited to range LO<x<HI, and without dups, this means that it can't have more than HI-LO-1 elements and therefore cannot have depth higher than HI-LO-1.

Now, if we know that the always-left path in the tree has depth M, then for each node, its right subtree can keep the range of values whose size is equivalent to left depth of this node. Since this range is limited, we are sure that right-depth of each node is no higher than the left depth, so we can skip probing it.

This means that we perform only M operations (scanning only left path), but the entire tree contains 1+2+...+M nodes, i.e. O(M*M).

Example is a tree whose left path, starting from root, is 21->15->10->6->3->2->1. Nodes from 15 to 6 may have right subtrees, but full size of such right subtree (and hence depth) is less than depth of left subtree of the same node, so don't need to be probed.

$\endgroup$

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.