5.Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

Solution I:

Approach:

Store the path till the elements and then compare the paths

class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {

        TreeNode *temp = root;
        vector<TreeNode *> v1;
        vector<TreeNode *> v2;
        int i;
        while (temp != NULL)
        {
            if (temp == p)
            {
                v1.push_back(temp);
                break;
            }
            else if (temp->val > p->val)
            {
                v1.push_back(temp);
                temp = temp->left;
            }
            else
            {
                v1.push_back(temp);
                temp = temp->right;
            }
        }

        temp = root;
        while (temp != NULL)
        {
            if (temp == q)
            {
                v2.push_back(temp);
                break;
            }
            else if (temp->val > q->val)
            {
                v2.push_back(temp);
                temp = temp->left;
            }
            else
            {
                v2.push_back(temp);
                temp = temp->right;
            }
        }

        if (v1.size() <= v2.size())
        {
            for (i = 0; i < v1.size(); i++)
            {
                if (v1[i] != v2[i])
                {
                    break;
                }
            }
            temp = v1[i - 1];
        }
        else
        {
            for (i = 0; i < v2.size(); i++)
            {
                if (v1[i] != v2[i])
                {
                    break;
                }
            }
            temp = v2[i - 1];
        }

        return temp;
    }
};

Time Complexity: O(h) but uses an extra space of O(n)

Solution II

Efficient Approach:

• If both the elements are greater move to right subtree

• If both the elements are smaller move to left subtree

• If one if smaller and one is greater then the current node is LCA

• If one of the value is found then that node is the LCA

class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {

        TreeNode *t = root;
        while (t != NULL)
        {
            if (p->val > t->val && q->val > t->val)
            {
                t = t->right;
            }
            else if (p->val < t->val && q->val < t->val)
            {
                t = t->left;
            }
            else if ((p->val < t->val && q->val > t->val) || (p->val > t->val && q->val < t->val))
            {
                break;
            }
            else if (p->val == t->val || q->val == t->val)
            {
                break;
            }
        }
        return t;
    }
};

Time Complexity: O(h) i.e O(log (n)) .