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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 4 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
General binary-tree LCAO(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.

  1. Return root when it is p or q; combine the left and right results.
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.

  1. While true: if p, q < node go left; else if p, q > node go right; else return node.
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, Smallest Common Region, Lowest Common Ancestor of a Binary Tree IV.

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.