Lowest Common Ancestor in Binary Search Tree

In a Binary Search Tree, you are given the values of two nodes. Write a code which will return the Lowest Common Ancestor of both the nodes.

For Example: If the given BST is as shown above and Nodes are 4 and 8,

The output should be: 5

4 and 8 has two common ancestors 5 and 10. But the lowest one is 5.
Solution:

Lowest Common Ancestor will be the Node which is ancestor to the nodes and whose value lies between the two nodes. 

For any two nodes in a BST, there is one and only one common ancestor whose value will be between the two nodes (i.e less than one and greater than the other). 

Algorithm:
FUNCTION FindCommonAncestor(Node * root, int a, int b)
    IF (value_at_root < a AND value_at_root > b) OR (value_at_root < b AND value_at_root < a)
        RETURN root
    ELSE
        IF (value_at_root < a AND value_at_root < b)
            RETURN FindCommonAncestor(root->left_sub_tree, a, b)
        ELSE
            RETURN FindCommonAncestor(root->right_sub_tree, a, b)
Code:
    /**
     *  Return the Least Common Ancestor (LCA) of Nodes with values a and b
     */
    Node* commonAncestor(Node* root, int a, int b)
    {
        // case when LCA doesn't exist
        if(root == NULL || root->data == a || root->data == b)
            return NULL;
        if( (root->data > a && root->data < b) || (root->data > b && root->data < a) )
            return root;
        // LCA will be on the LEFT sub-tree
        if(root->data > a && root->data > b)
            return commonAncestor(root->lptr, a, b);
        // LCA will be on the RIGHT sub-tree
        if(root->data < a && root->data < b)
            return commonAncestor(root->rptr, a, b);
    }

0 Comments

Leave a comment