Lowest Common Ancestor in a Binary Search Tree

Given values of two values n1 and n2 in a Binary Search Tree, find the Lowes Common Ancestor(LCA). You may assume that both the values exist in the tree.

Solution: Using Recursion

1. If both n1 and n2 are smaller than root, then LCA lies in left subtree
2. If both n1 and n2 are larger than root, then LCA lies in right subtree
3. If one node is smaller and the other one is larger then root is the LCA

Time complexity of above solution is O(h) where h is height of tree. And requires O(h) extra space for recursive function calls.

TreeNode * BinarySearchTree::findLCA(TreeNode *root, int n1, int n2) {
    if (!root) return NULL;

    // If both n1 and n2 are smaller than root, then LCA lies in left
    if (root->val > n1 && root->val > n2) {
        return findLCA(root->left, n1, n2);
    }

    // If both n1 and n2 are larger than root, then LCA lies in right
    if (root->val < n1 && root->val < n2) {
        return findLCA(root->right, n1, n2);
    }

    // If one node is smaller and the other one is larger then root is the LCA
    return root;
}

Solution: Optimized

We can improve this solution using iterative method.

TreeNode * BinarySearchTree::findLCAIterative(TreeNode *root, int n1, int n2) {
    TreeNode *lca = root;

    while (lca) {
        if (lca->val > n1 && lca->val > n2) {
            lca = lca->left;
        } else if (lca->val < n1 && lca->val < n2) {
            lca = lca->right;
        } else {
            break;
        }
    }

    return lca;
}