Lowest Common Ancestor of a Binary Search Tree

Medium Problem 75 of 151 Java and Python

Problem

Given a binary search tree and two of its nodes p and q, return their lowest common ancestor (LCA): the deepest node that has both p and q as descendants. A node counts as a descendant of itself.

Example 1

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

Example 2

Input: root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5], p = 2, q = 4
Output: 2
Why: A node can be its own ancestor.

Constraints

2 ≤ number of nodes ≤ 10⁵
All values are unique; p and q exist and are different.

Explanation

In a BST you know which side each value lives on. If both p and q are smaller than the current node, the LCA is in the left subtree; if both are larger, the right. Otherwise they split here (or one of them is this node), so this node is the LCA.

Approach 1 · Naive

Generic binary tree LCA

Time O(n)
Space O(h)

Ignore the ordering and use the general recursive LCA that searches both subtrees.

If the node is null, p or q, return it.
Recurse into both children; if both return a node, this is the LCA; otherwise return the non-null one.

Java

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

Python

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root is p or root is q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left or right

Approach 2 · Optimal

Walk down using BST order

Time O(h)
Space O(1)

Move left or right while both values are on the same side; stop at the split point.

Start at the root.
If both values are smaller, go left; if both are larger, go right.
Otherwise return the current node.

Java

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

Python

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        node = root
        while True:
            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

Complexity compared

Approach	Time	Space
Naive Generic binary tree LCA	O(n)	O(h)
Optimal Walk down using BST order	O(h)	O(1)

Key takeaways

Use the BST property whenever the problem gives you one; it usually turns O(n) into O(h).

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem