Time Complexity to find height of a BST

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?

• 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. Jul 30 '18 at 5:57
• @Sagnik-And the best case would also be $\Omega(n)$, right? Jul 30 '18 at 7:15

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.