Lowest Common Ancestor of a Binary Tree

MediumBinary Tree · Post-Order DFS🧩 Tree DFS LeetCode #236 ↗Updated Oct 30, 2026

Problem

Given a binary tree (not a BST) and two distinct nodes p and q that are both in it, return their lowest common ancestor: the deepest node that has both of them in its subtree. A node counts as an ancestor of itself.

Input[3,5,1,6,2,0,8], p=5, q=1Output3

Input[3,5,1,6,2,0,8], p=5, q=6Output5

Input[1,2], p=1, q=2Output1

2 ≤ n ≤ 10⁵ · all values unique · p ≠ q · p and q exist in the tree

Try it yourself

Java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Ask each subtree “did you see p or q?”. The first node (bottom-up) where the answer is yes from both sides — or that is itself p/q — is the LCA.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceTop-Down with Subtree Search

Time O(n²)Space O(h)

At each node, search the left subtree for p and q. Both on the left → go left; neither → go right; split → this node is the LCA. Each step re-scans a whole subtree, so a skewed tree costs O(n²).

Java

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == p || root == q) return root;
    boolean pLeft = contains(root.left, p), qLeft = contains(root.left, q);
    if (pLeft && qLeft) return lowestCommonAncestor(root.left, p, q);
    if (!pLeft && !qLeft) return lowestCommonAncestor(root.right, p, q);
    return root; // p and q are on different sides
}
private boolean contains(TreeNode node, TreeNode target) {
    if (node == null) return false;
    return node == target || contains(node.left, target) || contains(node.right, target);
}

Easy to justify, but searches the same nodes again at every level.

BetterParent Pointers + Ancestor Set

Time O(n)Space O(n)

Run an iterative DFS that records every node's parent until both p and q are seen. Walk up from p storing all its ancestors in a set; the first node on q's upward walk that is in the set is the LCA.

Java

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<>();
    for (TreeNode a = p; a != null; a = parent.get(a)) ancestors.add(a);
    while (!ancestors.contains(q)) q = parent.get(q);
    return q;
}

Linear and recursion-free, but needs a map and a set of up to n nodes.

OptimalRecursive Post-Order

Time O(n)Space O(h)

Return p/q as soon as you hit one, else null. If both children report non-null, p and q are split here → current node is the LCA. Otherwise bubble up the non-null report (it is already the LCA, or one target still waiting for the other).

Java

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; // split point
    return left != null ? left : right;
}

One pass, no extra structures — the expected interview answer.

Pro tip

Stopping at p is safe: if q lies below p, then p itself is the answer.

At a glance

Level	Approach	Time	Space
Brute Force	Top-Down with Subtree Search	`O(n²)`	`O(h)`
Better	Parent Pointers + Ancestor Set	`O(n)`	`O(n)`
Optimal	Recursive Post-Order	`O(n)`	`O(h)`

Common pitfalls

Comparing values with a BST rule (p.val < root.val) — this tree is not ordered.
Forgetting that a node can be its own ancestor (p is an ancestor of q).
Iterative version: walking up q before the parent map contains both nodes.

Interview tips

Ask: BST or plain tree? Are p and q guaranteed to exist?
Explain the three return cases: both non-null, one non-null, none.
Offer the parent-pointer version if recursion depth (skewed, n=10⁵) is a concern.

Pattern

Post-order DFS returning a “found” signal → combine evidence from both subtrees to locate a meeting node.

My notes saved in this browser