Lowest Common Ancestor of a Binary Search Tree

mediumTrees: BST & Advanced13 stepsJava · Python · C++

In a BST, if both p and q are smaller than a node, their LCA is in the left subtree; if both are bigger, it's in the right subtree. The first node where they split (or that equals one of them) is the LCA.

▶ Watch the animated trace

Traced input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 3, q = 5 → 4. Original problem: neetcode.io/problems/lowest-common-ancestor-in-binary-search-tree

Complexity

BestO(1)

AverageO(h)

WorstO(h)

SpaceO(1)

Iterative walk down one path.

Key idea

The BST ordering tells you which side both nodes are on.
The split point, where p and q go different ways, is the lowest common ancestor.
A node can be its own ancestor: if p equals the current node, it's the answer.

Common mistakes

Ignoring the BST property and using the general binary-tree solution (works, but misses the point).
Comparing node references instead of values when the inputs are values.

Solution

Java

TreeNode lowestCommonAncestorBST(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;
}

Python

def lowestCommonAncestorBST(root: TreeNode, p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    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
    return None

C++

TreeNode* lowestCommonAncestorBST(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

Each one has its own trace in the interactive view.

Case	Input	Answer
Split at the root p is left, q is right.	`root = [6, 2, 8, 0, 4, 7, 9], p = 2, q = 8`	`6`
One node is the ancestor 2 is an ancestor of 4, so 2 is the LCA.	`root = [6, 2, 8, 0, 4, 7, 9], p = 2, q = 4`	`2`
Two nodes The root is p itself.	`root = [2, 1], p = 2, q = 1`	`2`