Write a function to return Lowest Common Ancestor in a Binary Search Tree. | Atrenta written Question

In a binary search tree, write a c function to find the lowest common ancestor. You may assume that both values already exist in the tree.

           / \
         1    4
             / \
           3    5
Lowest Comman ancestor of 1 and 3 is 2 .

Algorithm :
While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side. Code :

/* Function to find least comman ancestor of n1 and n2 */
int leastCommanAncestor(struct node* root, int n1, int n2)
  /* If we have reached a leaf node then LCA doesn't exist
     If root->data is equal to any of the inputs then input is
     not valid.  */
  if(root == NULL || root->data == n1 || root->data == n2)
    return -1; 
  /* If any of the input nodes is child of the current node
     we have reached the LCA. For example, in the above figure
     if we want to calculate LCA of 4 and 5, recursion should
     terminate when we reach 2*/
  if((root->right != NULL) &&
    (root->right->data == n1 || root->right->data == n2))
    return root->data;
  if((root->left != NULL) &&
    (root->left->data == n1 || root->left->data == n2))
    return root->data;    
  if(root->data > n1 && root->data < n2)
    return root->data;
  if(root->data > n1 && root->data > n2)
    return leastCommanAncestor(root->left, n1, n2);
  if(root->data < n1 && root->data < n2)
    return leastCommanAncestor(root->right, n1, n2);

Time complexity: O(Logn) for a balanced BST and O(n) for a unbalanced BST.

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |