Lowest Common Ancestor of a Binary Search Tree

Medium Trees & BST LCA Original on LeetCode

Lowest Common Ancestor of a Binary Search Tree is a medium trees & bst problem solved with the lca pattern. The best approach, optimal (walk down using the bst order), runs in O(h) time and O(1) space. Below are 2 approaches in Java, from general binary-tree lca up.

Problem

Find the lowest common ancestor of two nodes in a binary search tree. Use the BST ordering to do better than the general method.

Examples

Example 1

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 8
Output: 6

Example 2

Input: same tree, p = 2, q = 4
Output: 2

Constraints

The tree has 2 to 10^5 nodes; it is a valid BST with unique values.
p and q exist.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
General binary-tree LCA	`O(n)`	`O(h)`
Optimal (walk down using the BST order)	`O(h)`	`O(1)`

1General binary-tree LCA

TimeO(n)

SpaceO(h)

Ignore the BST property and use the postorder LCA method. It is correct but visits more nodes than needed.

Return root when it is p or q; combine the left and right results.

Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q), r = lowestCommonAncestor(root.right, p, q);
        return l != null && r != null ? root : l != null ? l : r;
    }
}

2Optimal (walk down using the BST order)

TimeO(h)

SpaceO(1)

Start at the root. If both p and q are smaller, go left; if both are larger, go right. The first node where they split (or that equals one of them) is the LCA.

While true: if p, q < node go left; else if p, q > node go right; else return node.

Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode cur = root;
        while (true) {
            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;
        }
    }
}

Edge cases to test

p is an ancestor of q

Hints

Hint 1

If both values are smaller than the node, the LCA is on the left; if both are larger, on the right. Otherwise you are at the split point.

FAQ

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

Optimal (walk down using the BST order) runs in O(h) time and O(1) extra space.

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

It is a trees & bst problem that uses the lca pattern. Other problems with the same pattern: Lowest Common Ancestor of a Binary Tree.

Is there a brute force solution for Lowest Common Ancestor of a Binary Search Tree?

Yes. General binary-tree LCA takes O(n) time and O(h) space. Ignore the BST property and use the postorder LCA method.

Which edge cases should I test for Lowest Common Ancestor of a Binary Search Tree?

p is an ancestor of q.