52.Lowest Common Ancestor of a BST

MediumBlind 75Trees · 7/15

Problem

Given a binary search tree (BST) and two nodes p and q in it, return their lowest common ancestor (LCA): the deepest node that has both p and q as descendants. A node is allowed to be a descendant of itself, so if p is an ancestor of q, the answer is p.

Examples

Input:  root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the left subtree of 6 and 8 is in the right subtree, so they split at 6.

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

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, and both p and q exist in the BST.

💡 Key Insight

In a BST, everything smaller than a node lives on its left and everything larger lives on its right. Starting from the root, if both p and q are smaller, the LCA is in the left subtree; if both are larger, it is in the right subtree. The first node where they split (one on each side, or the node equals one of them) is the LCA. That gives an O(h) walk from the root with O(1) extra space.

Generic Binary Tree LCA

TimeO(n)SpaceO(h)

Intuition

Ignore the BST ordering and solve the general problem: recursively search both subtrees. If a node is p or q, return it. If the left and right recursive calls both return non-null, the current node is where the two targets split, so it is the LCA. Otherwise, pass up whichever side found something.

Algorithm

If root is null, p or q, return root.
left = lca(root.left), right = lca(root.right).
If both are non-null, return root.
Return left != null ? left : right.

Visualization

p = 2, q = 8 on root 6

lca(6): left  = lca(2) -> returns 2 (node is p)
        right = lca(8) -> returns 8 (node is q)
        both non-null -> answer 6

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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; // p and q found on different sides
        }
        return left != null ? left : right;
    }
}

Complexity

Time: O(n) — in the worst case every node is visited; the BST property is never used.
Space: O(h) — recursion depth.

Recursive BST Descent

TimeO(h)SpaceO(h)

Intuition

Use the ordering. Compare p.val and q.val with root.val: if both are smaller, recurse left only; if both are larger, recurse right only; otherwise the current node separates them and is the LCA. We now follow a single path instead of exploring the whole tree.

Algorithm

If p.val < root.val and q.val < root.val, return lca(root.left, p, q).
If p.val > root.val and q.val > root.val, return lca(root.right, p, q).
Otherwise return root.

Visualization

p = 3, q = 5 on root 6

6: both < 6  -> go left
2: both > 2  -> go right
4: 3 < 4 < 5 -> split -> answer 4

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
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; // p and q split here (or root is one of them)
    }
}

Complexity

Time: O(h) — one step down per level; O(log n) balanced, O(n) skewed.
Space: O(h) — the recursion stack along that path.

Iterative BST DescentOptimal

TimeO(h)SpaceO(1)

Intuition

Approach 2 is tail-recursive: each call just hands off to one child. Replace the recursion with a loop that moves a pointer node down the tree, and the stack disappears entirely.

Algorithm

Set node = root.
Loop:
- If both values are smaller than node.val, set node = node.left.
- Else if both are larger, set node = node.right.
- Else return node.

Dry Run

flowchart TD
    N6["6<br/>3 and 5 both < 6 -> go left"] --> N2["2<br/>3 and 5 both > 2 -> go right"]
    N6 --> N8["8"]
    N2 --> N0["0"]
    N2 --> N4["4<br/>3 < 4 < 5 -> split<br/>return 4"]
    N8 --> N7["7"]
    N8 --> N9["9"]
    N4 --> N3["3 (p)"]
    N4 --> N5["5 (q)"]

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node != null) {
            if (p.val < node.val && q.val < node.val) {
                node = node.left;      // both targets in left subtree
            } else if (p.val > node.val && q.val > node.val) {
                node = node.right;     // both targets in right subtree
            } else {
                return node;           // first split point is the LCA
            }
        }
        return null; // unreachable when p and q are in the tree
    }
}

Complexity

Time: O(h) — a single root-to-LCA walk.
Space: O(1) — only one pointer.

Complexity Comparison

Approach	Time	Space
Generic Binary Tree LCA	O(n)	O(h)
Recursive BST Descent	O(h)	O(h)
Iterative BST Descent	O(h)	O(1)

Common Pitfalls

Forgetting that a node is its own descendant: when node == p (or q), it is already the LCA — the "else" branch handles this because the strict comparisons fail.
Using <= / >= in the descent conditions, which walks past p or q when one of them equals the current node.
Ignoring the BST property and paying O(n) when O(h) is possible.
Values go down to -10^9; subtracting values (e.g. (p.val - node.val) * (q.val - node.val) > 0) can overflow int — compare instead, or use long.