Course4all

Lowest Common Ancestor of a Binary Tree

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trees.

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

  1. Define contains(node, target) helper.
  2. For current root, if root is p or q, it might be LCA.
  3. If contains(root.left, p & q) is true, move to left child.
  4. If contains(root.right, p & q) is true, move to right child.
  5. If they are split, root is LCA.
⏱ O(N^2) (Checking containment for each node)💾 O(H)

Detailed Dry Run

NodeLeft contains p, q?Right contains p, q?Decision
3nonoSplit! 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

  1. BFS/DFS to build parentMap until both p and q are found.
  2. Collect all ancestors of p in a set.
  3. 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

  1. If a subtree returns a non-null node, it means p or q was found in that subtree.
  2. If both subtrees return non-null, the current node is the Lowest Common Ancestor.
  3. 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

NodeLeft ResultRight ResultPass Up
5pnullp
1nullqq
35(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.

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionBinary Tree Level Order Traversal
Next Question →Binary Tree Zigzag Level Order Traversal