Lowest Common Ancestor of a BST

Approach Summary

If both p and q are smaller than root, LCA is in left subtree. If both larger, right subtree. Otherwise root is the LCA.

Full Solution & Approach

The BST property lets you find the lowest common ancestor without recursion or extra space: the LCA is the first node whose value lies between p.val and q.val (inclusive). Walk from the root. If both p and q are smaller than the current node, the LCA is in the left subtree, so descend left. If both are larger, descend right. Otherwise — p and q are on different sides, or one of them equals the current node — the current node is the LCA, because any deeper node would separate the two. This is a single downward path, so it runs in O(h) time and O(1) space. Compare with the binary-tree (non-BST) version, which needs recursion and a post-order search — the BST version is dramatically simpler precisely because of the ordering invariant.

The walk follows a single root-to-leaf path — O(h) time, O(log n) for balanced trees. No recursion — O(1) space.

Solution Code

Solution

def lowest_common_ancestor(root, p, q):
    cur = root
    while cur:
        if p.val < cur.val and q.val < cur.val:
            cur = cur.left
        elif p.val > cur.val and q.val > cur.val:
            cur = cur.right
        else:
            return cur
    return None

function lowestCommonAncestor(root, p, q) {
  let cur = root;
  while (cur) {
    if (p.val < cur.val && q.val < cur.val) cur = cur.left;
    else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
    else return cur;
  }
  return null;
}

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode cur = root;
    while (cur != null) {
        if (p.val < cur.val && q.val < cur.val) cur = cur.left;
        else if (p.val > cur.val && q.val > cur.val) cur = cur.right;
        else return cur;
    }
    return null;
}

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* cur = root;
    while (cur) {
        if (p->val < cur->val && q->val < cur->val) cur = cur->left;
        else if (p->val > cur->val && q->val > cur->val) cur = cur->right;
        else return cur;
    }
    return nullptr;
}

Edge Cases to Watch

One node is an ancestor of the other — the ancestor is the LCA
p equals q — that node is the LCA
The root is the LCA — p and q split across subtrees
Both nodes on the same side — the walk descends straight down

How to Recognize This Pattern

LCA in BST using BST property

Complexity Analysis

Time Complexity

O(h)

Space Complexity

O(1)