Data Structures-Self Doubt

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

int height(struct node *root)

{

  if(root==NULL) return 0;

  if(root->leftChild==NULL && root->rightChild==NULL)

  return 0;

  else

  { int c=0,lh,rh;

    lh=height(root->leftChild); ............(A)

    rh=height(root->rightChild); ...............(B)

    c=1+max(lh,rh);........................(C)

     return c;

   } //end of else

  
} //end of function height.

So, in best Case, my recurrence would become

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

$T(\frac{n}{2})$ for each of line A and B, and constant time for Line C, and even for 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 to be $O(n)$.

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

Was my claim correct?

Comments

when u r calling n/2 element recursively, that means u r doing binary search

Is here u using binary search?

---

Ok mam I accept i am dumb, please tell me what would be the best case for above code for binary search tree height and it's recurrence, please.

---

As it searching linearly every node, I think recurrence will be T(n)=T(n−1)+c