GATE Overflow Test Series | Data Structures | Test 1 | Question: 20

Question

What is the best time complexity (not the best case input but the best algorithm which will work for any input) for finding the lowest common ancestor for two keys $a$ and $b$ in a binary search tree of $n$ nodes and height $h$?

• A. $\Theta(n)$
• B. $\Theta(n \log n)$
• C. $O(h)$
• D. $\Omega(n)$

Answer 1

We can do a recursive function as follows:

struct node * find(struct node *root,int  val1, int val2)
{
   if(!root) return NULL;
   if(root->val > val1 && root -> val > val2)
   {
      return  find(root->left, val1, val2);
   }
   if(root->val < val1 && root -> val < val2)
   {
        return find(root->right, val1, val2);
   }
   return root;
}

Comments

sir can you please explain  the logic of the algorithm ……. it would be really helpful ...thanks

---

It is similar concept of least upper bound in set theory.