Lowest Common Ancestor of a Binary Tree

Master this topic with zero to advance depth.

Lowest Common Ancestor of a Binary Tree

Find LCA.

Medium

Approach 1

Level I: Brute Force (Recursive Containment Check)

Intuition

The Lowest Common Ancestor (LCA) is the node where p and q first reside in different subtrees (one in left, one in right), or the node itself is one of p or q. A brute force approach checks for every node if it contains p and q in its subtrees.

Thought Process

Define contains(node, target) helper.
For current root, if root is p or q, it might be LCA.
If contains(root.left, p & q) is true, move to left child.
If contains(root.right, p & q) is true, move to right child.
If they are split, root is LCA.

⏱ O(N^2) (Checking containment for each node)💾 O(H)

Detailed Dry Run

Node	Left contains p, q?	Right contains p, q?	Decision
3	no	no	Split! 3 is LCA

java

public class Main {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        boolean leftP = contains(root.left, p), leftQ = contains(root.left, q);
        if (leftP && leftQ) return lowestCommonAncestor(root.left, p, q);
        boolean rightP = contains(root.right, p), rightQ = contains(root.right, q);
        if (rightP && rightQ) return lowestCommonAncestor(root.right, p, q);
        return root;
    }
    private boolean contains(TreeNode root, TreeNode target) {
        if (root == null) return false;
        if (root == target) return true;
        return contains(root.left, target) || contains(root.right, target);
    }
}

Approach 2

Level II: Iterative with Parent Map

Intuition

We can traverse the tree and store each node's parent in a hash map. Once we've found both nodes p and q, we can backtrack from p to the root, storing all ancestors in a set. Then, we backtrack from q the first ancestor that exists in that set is the LCA.

Logic

BFS/DFS to build parentMap until both p and q are found.
Collect all ancestors of p in a set.
Pull upwards from q until an ancestor exists in p's ancestor set.

⏱ O(N) (visiting each node once)💾 O(N) (parent map and ancestor set)

Detailed Dry Run

p=5, q=1. parents={5:3, 1:3, 3:null}. p-ancestors={5, 3}. q's parent 3 is in set -> LCA=3.

java

public class Main {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        parent.put(root, null);
        stack.push(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        while (!ancestors.contains(q)) q = parent.get(q);
        return q;
    }
}

Approach 3

Level III: Optimal (Post-order Recursion)

Intuition

Thought Process

Instead of checking containment repeatedly, we can do a single bottom-up traversal. We ask each child: "Do you see p or q?".

Logic

If a subtree returns a non-null node, it means p or q was found in that subtree.
If both subtrees return non-null, the current node is the Lowest Common Ancestor.
If only one subtree is non-null, pass that result up.

Pattern

Bottom-Up DFS: Aggregate information from children to decide for the parent.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left Result	Right Result	Pass Up
5	p	null	p
1	null	q	q
3	5(p)	1(q)	3 (LCA)

java

public class Main {
    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;
    }
}

⚠️ Common Pitfalls & Tips

This approach assumes both p and q exist in the tree. If they might not exist, a double-check pass is required.

← Previous QuestionBinary Tree Level Order Traversal

Next Question →Binary Tree Zigzag Level Order Traversal

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.