Lowest Common Ancestor in 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 v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]

    _______6______
   /              \
___2__          ___8__

/ \ / \ 0 _4 7 9 / \ 3 5

Example 1:

Input: root, p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6. Example 2:

Input: root, p = 2, q = 4 Output: 2

Solution: Recursion

1. If both nodes are smaller than root, then LCA lies in left subtree
2. If both nodes 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

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;
        if (p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        } 
        return root;
    }

Solution: Iterative

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) return NULL;

    while (root) {
        if (root->val < p->val && root->val < q->val) {
            root = root->right;
        } else if (root->val > p->val && root->val > q->val) {
            root = root->left;
        } else {
            break;
        } 
    }
    return root;
}