Lowest Common Ancestor of a Binary Search Tree

medium
TreesTreeBinary TreeDepth-First Search

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes p and q in the BST. The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants (where we allow a node to be a descendant of itself).

Examples

Example 1

  • Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
  • Output: 6
  • Explanation: The LCA of nodes 2 and 8 is 6.

Example 2

  • Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
  • Output: 2
  • Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself.

Example 3

  • Input: root = [2,1], p = 2, q = 1
  • Output: 2

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive BST Traversal

Intuition

The BST property gives us a powerful way to find the LCA. If both p and q are smaller than the current node, the LCA must be in the left subtree. If both are greater, the LCA must be in the right subtree. If one is on each side (or one equals the current node), then the current node is the LCA. This works because the BST ordering guarantees that the split point is exactly the lowest common ancestor. We do not need to search the entire tree -- we follow a single path from root to the LCA.

Algorithm

  1. Start at the root node.
  2. If both p.val and q.val are less than root.val, recurse into the left subtree.
  3. If both p.val and q.val are greater than root.val, recurse into the right subtree.
  4. Otherwise, root is the split point where p and q diverge (or one of them equals root), so return root.
TimeO(h) where h is the height of the treeSpaceO(h) for the recursion stack

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val < root->val && q->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        if (p->val > root->val && q->val > root->val) {
            return lowestCommonAncestor(root->right, p, q);
        }
        return root;
    }
};
Java 21
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return root;
    }
}
Python 3.12
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    if p.val < root.val and q.val < root.val:
        return lowestCommonAncestor(root.left, p, q)
    if p.val > root.val and q.val > root.val:
        return lowestCommonAncestor(root.right, p, q)
    return root
Go 1.26
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if p.Val < root.Val && q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    if p.Val > root.Val && q.Val > root.Val {
        return lowestCommonAncestor(root.Right, p, q)
    }
    return root
}
Approach 2

Iterative Traversal

Intuition

We can convert the recursive approach to an iterative one, eliminating the recursion stack. Starting from the root, we walk down the tree following the same logic: go left if both values are smaller, go right if both are larger, and stop when the values split. This uses O(1) extra space since we only need a single pointer to track our position in the tree.

Algorithm

  1. Set the current node to root.
  2. While current is not null, check if both p.val and q.val are less than current.val. If so, move to current.left.
  3. If both p.val and q.val are greater than current.val, move to current.right.
  4. Otherwise, current is the LCA. Return it.
TimeO(h) where h is the height of the treeSpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* current = root;
        while (current != nullptr) {
            if (p->val < current->val && q->val < current->val) {
                current = current->left;
            } else if (p->val > current->val && q->val > current->val) {
                current = current->right;
            } else {
                return current;
            }
        }
        return nullptr;
    }
};
Java 21
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;
        while (current != null) {
            if (p.val < current.val && q.val < current.val) {
                current = current.left;
            } else if (p.val > current.val && q.val > current.val) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }
}
Python 3.12
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    current = root
    while current:
        if p.val < current.val and q.val < current.val:
            current = current.left
        elif p.val > current.val and q.val > current.val:
            current = current.right
        else:
            return current
    return None
Go 1.26
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    current := root
    for current != nil {
        if p.Val < current.Val && q.Val < current.Val {
            current = current.Left
        } else if p.Val > current.Val && q.Val > current.Val {
            current = current.Right
        } else {
            return current
        }
    }
    return nil
}

Frequently asked questions

What is the optimal time complexity of Lowest Common Ancestor of a Binary Search Tree?

The most efficient approach in this guide ("Iterative Traversal") runs in O(h) where h is the height of the tree time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Lowest Common Ancestor of a Binary Search Tree use?

Lowest Common Ancestor of a Binary Search Tree is a medium-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Lowest Common Ancestor of a Binary Search Tree be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(h) for the recursion stack, while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Validate Binary Search Tree

Original problem: leetcode.com

Loading editor...
Input
root=
[6,2,8,0,4,7,9,null,null,3,5]
p=
2
q=
8
Expected Output
6