Time Complexity to find height of a BST

Question

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?

Answer 1

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.