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?