Lowest Common Ancestor of a Binary Search Tree

How it works

This is the iterative version of finding the Lowest Common Ancestor (LCA) in a Binary Search Tree (BST). Because a BST is ordered:

• Left subtree < node < right subtree

We can decide where both nodes lie just by comparing values.

• If p and q are both greater than the current node -> move right.
• If they are both smaller -> move left.
• If they split (one on each side) or one equals the current node -> current node is the LCA, because it's the first node where their paths diverge.

This avoids recursion and simply walks down the tree until the split point is found.

Steps

1. Set cur = root.
2. While cur is not null:
   • If p.val and q.val are both greater than cur.val -> go right.
   • Else if both are smaller -> go left.
   • Otherwise:
     • You've found the first node where their paths separate -> return cur (the LCA).
3. Return null if tree is empty (should not happen for valid input).

Complexity

• Time complexity: O(h)
• Space complexity: O(1)

Where h is the height of the tree.

Things to watch for

Ignoring BST Properties

A common mistake is treating this problem like a general binary tree LCA problem. In a BST, values are ordered (left < node < right), which allows us to determine the direction to search based on value comparisons alone. Using a generic DFS approach that checks both subtrees wastes time and ignores the BST structure that makes O(h) solutions possible.

Incorrect Comparison Logic

When comparing p and q values against the current node, be careful with the boundary conditions. The LCA is found when the current node's value lies between p.val and q.val (inclusive). A common bug is using strict inequalities everywhere, which fails when p or q equals the current node. Remember: if p.val <= root.val <= q.val (or vice versa), the current node is the LCA.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        cur = root

        while cur:
            if p.val > cur.val and q.val > cur.val:
                cur = cur.right
            elif p.val < cur.val and q.val < cur.val:
                cur = cur.left
            else:
                return cur

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

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

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