Lowest Common Ancestor of a BST — One-Line Guided Walk

LCA on a BST is the gentler twin of LCA on a generic binary tree. On a generic binary tree, finding the LCA requires a careful post-order trick. On a BST, the ordering hands you the answer almost for free: the LCA is the first node whose value sits between the two targets.

The Problem

Given the root of a BST and two nodes p and q (guaranteed to exist), return their lowest common ancestor — the deepest node that has both p and q as descendants. By convention, a node is a descendant of itself, so if p is an ancestor of q, the answer is p.

Intuition

Walk from the root and exploit ordering:

• If both p and q are less than the current node, the LCA is in the left subtree.
• If both are greater, it is in the right subtree.
• Otherwise the current node splits them — it is the LCA.

That third case also covers “one of them equals the current node” because the strict comparisons fall through.

Explanation with Example

Take the BST [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5] with p = 2 and q = 8.

• Start at 6. p.val = 2 < 6 and q.val = 8 > 6. They split here. Return 6.

Now try p = 2, q = 4.

• Start at 6. Both targets are less than 6. Go left.
• At 2. p equals the current node. Since p.val is not strictly less and not strictly greater, the condition falls through to return node. Answer: 2.

The “node is a descendant of itself” rule is exactly what makes the early termination clean.

              6   <-- p=2 < 6 and q=8 > 6  SPLIT -> LCA = 6
           / \
          2   8
         / \ / \
        0  4 7  9
          / \
         3   5

decision rule at each node:
both targets < node.val  --> go left
both targets > node.val  --> go right
otherwise (split or equal) --> return node

Code

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

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

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

Edge Cases

• One node is an ancestor of the other — handled, because the comparison falls through when one value equals the current node.
• p and q are the same node — return that node.
• A skewed BST that is essentially a sorted linked list — still O(h), where h equals n. Worth flagging in interview if you suspect adversarial input.
• The tree contains duplicates — the standard problem forbids this; if asked, you must define BST strictness first.

Complexity Analysis

Time is O(h) where h is tree height. Balanced BST gives O(log n), skewed BST gives O(n). Space is O(1) for the iterative version and O(h) for the recursive one. The brute-force generic-tree solution remains O(n) time and O(n) space.

If the comparison of “O(h) vs O(n)” feels fuzzy, the Big-O notation post covers how to talk about height-bound complexities cleanly.

How to Explain It in an Interview

State the property first: “In a BST, the LCA of p and q is the first node on the root-to-leaf path whose value lies between them, inclusive.” Then derive the three cases. Mention you could fall back to the generic LCA approach if the BST invariant were broken. Close with the space trade — recursive is shorter, iterative wins on stack frames.

Related Problems

• Lowest Common Ancestor of a Binary Tree (the generic version)
• LCA when nodes may not exist
• LCA with parent pointers
• Validate Binary Search Tree

For deeper coverage of traversals that LCA-style problems lean on, see Binary Tree Traversals.

Wrap up

LCA on a BST is the rare problem where the optimal solution is shorter than the brute force and runs in less memory. The lesson is to always ask: what invariant does the data structure give me? Here, sorted order collapses an entire DFS into a guided walk. Lock in the three-case template and this problem becomes a freebie.