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