LeetCode 236 Lowest Common Ancestor of a Binary Tree: Every Approach Explained

LeetCode 236 is the canonical "what does each node return to its parent" tree problem. The accepted solution is so short that many candidates memorise it without being able to explain the case where p is an ancestor of q, or why the function can return a node that is not actually the LCA midway through the recursion. Interviewers know this, so they probe exactly those points and then pivot to variants. This guide covers the solution, the proof, a dry run, and the four variants you are most likely to face.

The Problem: Lowest Common Ancestor of a Binary Tree

Given the root of a binary tree (not a BST) and two nodes p and q that are guaranteed to exist in it, return their lowest common ancestor. LeetCode's definition: the LCA is the lowest node in the tree that has both p and q as descendants, where a node is allowed to be a descendant of itself. Constraints: 2 to 10⁵ nodes, all values unique, p != q.

We will use this tree throughout (the same one as LeetCode's examples):

Note LCA(5, 4) = 5. Node 5 is an ancestor of 4, and 5 is its own descendant, so it is the lowest node containing both. This "ancestor case" is where most explanations get vague.

Warm-Up: Compare Root-to-Node Paths

The most intuitive approach: find the path from the root to p and the path from the root to q, then walk both paths together until they diverge. The last common node is the LCA.

def lca_by_paths(root, p, q):
    def path_to(node, target, path):
        if node is None:
            return False
        path.append(node)
        if node is target:
            return True
        if path_to(node.left, target, path) or path_to(node.right, target, path):
            return True
        path.pop()
        return False

    pp, pq = [], []
    path_to(root, p, pp)
    path_to(root, q, pq)
    lca = None
    for a, b in zip(pp, pq):
        if a is not b:
            break
        lca = a
    return lca

Paths for 7 and 4: [3, 5, 2, 7] and [3, 5, 2, 4]. They agree on 3, 5, 2 and diverge after, so the LCA is 2. This is O(n) time and O(h) extra space for the paths, and it is a perfectly good first answer to say out loud. Its weaknesses: two traversals, extra lists, and more code to get right. The single-pass recursion below does better.

The Recursive Solution: One Postorder Pass

Define f(node) as follows:

• If node is null, return null.
• If node is p or q, return node.
• Otherwise compute L = f(node.left) and R = f(node.right). If both are non-null, return node. Otherwise return whichever is non-null (or null if both are).

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;
    }
}

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

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None 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

Complexity: each node is visited at most once, so O(n) time. The recursion stack is O(h): O(log n) for balanced trees, O(n) for a skewed tree. For 10⁵ nodes in a skewed tree, Python's default recursion limit of 1,000 is a real problem outside LeetCode; mention it, and offer the iterative parent-map approach shown later.

Compare nodes by identity (== on references in Java and C++, is in Python), not by value. Values are unique on LeetCode, but identity is the correct semantic and avoids surprises if values repeat in a follow-up.

Why the Recursion Is Correct (The Part Interviewers Probe)

The function's return value means different things in different situations. Pin down the contract precisely:

Prove the contract by induction on subtree size. The null case is trivial. Now take a non-null node and assume the contract holds for its children.

1. node is p (or q). We return node immediately. If the other target is somewhere below, then node contains both, and node is their LCA because it is an ancestor of the other target and of itself, and nothing lower contains node. If the other target is not below, node contains exactly one target and we return that target. Either way the contract holds, without searching the subtree.
2. Both L and R non-null. By the contract on children, each side contains exactly one target (a side cannot contain both, or the other side would contain none). So p and q are split across node's two subtrees. No descendant of node contains both, so node is the LCA. Return node.
3. Exactly one of L, R non-null. Say L. Then the right subtree has neither target, and the left has one or both. If it has both, L is their LCA, and it is also the LCA within node's subtree. If it has one, L is that target. Pass L up. The contract holds.
4. Both null. Neither target is below and node is neither target. Return null.

At the root, the problem guarantees both targets exist, so f(root) returns the LCA. Note that in the middle of the recursion, a non-null return might be "just p" rather than an LCA. That is fine; the contract says what it means.

The short-circuit in case 1 is why the code never explores below p. It is also why the algorithm breaks if p or q might be missing: if p is found and q does not exist, the function happily returns p as if it were the LCA. We fix that later.

Dry Run: LCA(7, 4) and LCA(5, 4)

LCA(7, 4) on the tree above. Postorder, so children resolve before parents:

LCA(5, 4): f(3) calls f(5). Node 5 is p, so f(5) returns 5 without ever visiting 6, 2, 7 or 4. f(1) returns null. At node 3, L = 5 and R = null, so 5 is passed up and returned. Correct, because 4 is inside 5's subtree. The algorithm never verified that, and it did not need to, because the problem guarantees q exists.

Variant: Nodes With Parent Pointers (LeetCode 1650)

Suppose each node has a parent field and you are given only p and q, not the root. Walking up from p gives a linked list ending at the root, and so does walking up from q. The two lists merge at the LCA. This is exactly Intersection of Two Linked Lists (LeetCode 160).

Option A: hash set of ancestors

Walk from p to the root, adding each node to a set. Then walk up from q; the first node found in the set is the LCA. O(h) time, O(h) space.

Option B: two pointers with a switch, O(1) space

Move pointer a up from p and pointer b up from q. When a pointer passes the root (reaches null), restart it at the other starting node. Both pointers travel depth(p) + depth(q) steps in total, so they line up and meet exactly at the LCA.

def lca_with_parent(p, q):
    a, b = p, q
    while a is not b:
        a = a.parent if a else q
        b = b.parent if b else p
    return a

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node a = p, b = q;
        while (a != b) {
            a = (a == null) ? q : a.parent;
            b = (b == null) ? p : b.parent;
        }
        return a;
    }
}

Why it works: let the path from p up to the LCA have length x, from q up to the LCA have length y, and from the LCA up to the root (inclusive) have length z. Pointer a covers x + z, switches, then covers y to reach the LCA: x + z + y. Pointer b covers y + z, switches, then x: the same total. They arrive together. Because both p and q are in the same tree, the paths always intersect, so the loop terminates.

This variant also gives you an iterative fallback for LC 236 when recursion depth is a concern: do one BFS or iterative DFS from the root to build a parent hash map, then apply Option A. O(n) time, O(n) space, no recursion.

Variant: Lowest Common Ancestor in a BST (LeetCode 235)

When the tree is a binary search tree, you do not need to search both subtrees. Values tell you where p and q are:

• If both p and q are smaller than node, the LCA is in the left subtree.
• If both are larger, it is in the right subtree.
• Otherwise they split here (or one of them equals node), so node is the LCA.

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;
            else if (p.val > node.val && q.val > node.val) node = node.right;
            else return node;
        }
        return null;
    }
}

def lca_bst(root, p, q):
    node = root
    while node:
        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
    return None

O(h) time and O(1) space with the loop. On the BST [6,2,8,0,4,7,9,null,null,3,5], LCA(2, 8) is 6 (they split at the root), and LCA(2, 4) is 2 (at node 2, p equals node, so the "otherwise" branch fires). A common mistake is using the general LC 236 solution here. It is correct but O(n), and the interviewer will ask why you ignored the BST property. More BST techniques are in binary search tree interview problems.

Variant: When p or q Might Not Exist (LeetCode 1644)

Drop the guarantee that both nodes are present, and return null if either is missing. The short-circuit "return node if it is p or q" is now unsafe, because finding p does not prove q exists.

The fix: traverse the whole tree, count how many targets you actually find, and do the LCA bookkeeping in postorder (after recursing into children), so the search never stops early.

def lca_maybe_missing(root, p, q):
    found = 0
    def dfs(node):
        nonlocal found
        if node is None:
            return None
        left = dfs(node.left)
        right = dfs(node.right)
        if node is p or node is q:
            found += 1
            return node
        if left and right:
            return node
        return left or right
    ans = dfs(root)
    return ans if found == 2 else None

Because the children are explored before checking whether node is a target, both p and q are always discovered even when one is an ancestor of the other. Still O(n) time. A similar generalisation is LCA of a set of nodes (LeetCode 1676): put the targets in a hash set and replace node is p or node is q with a set membership check; the rest of the original recursion stays the same.

Binary Lifting: Many LCA Queries on One Tree

If the interviewer asks "what if there are 10⁵ queries on the same tree?", running the O(n) recursion per query costs O(n · Q), around 10¹⁰ operations. You need preprocessing.

Binary lifting stores up[k][v], the 2^k-th ancestor of v. up[0][v] is the parent, and up[k][v] = up[k-1][ up[k-1][v] ]: jumping 2^k is two jumps of 2^k-1. With depths computed by one DFS or BFS, a query works in two phases:

1. Equalise depths. Lift the deeper node by the depth difference d, using the binary representation of d: for every bit k set in d, jump up[k].
2. Lift together. If the nodes are now equal, that is the LCA. Otherwise, for k from high to low, if up[k][u] != up[k][v], jump both. They stop just below the LCA, so return up[0][u].

#include <vector>
#include <utility>
using namespace std;

struct LCA {
    int LOG;
    vector<vector<int>> up;
    vector<int> depth;

    // adj: adjacency list of a tree with n nodes, rooted at root
    LCA(const vector<vector<int>>& adj, int root) {
        int n = adj.size();
        LOG = 1;
        while ((1 << LOG) < n) ++LOG;
        up.assign(LOG, vector<int>(n, root));
        depth.assign(n, 0);
        // iterative DFS to avoid stack overflow on deep trees
        vector<int> stack = {root};
        vector<bool> seen(n, false);
        seen[root] = true;
        while (!stack.empty()) {
            int v = stack.back(); stack.pop_back();
            for (int u : adj[v]) if (!seen[u]) {
                seen[u] = true;
                up[0][u] = v;
                depth[u] = depth[v] + 1;
                stack.push_back(u);
            }
        }
        for (int k = 1; k < LOG; ++k)
            for (int v = 0; v < n; ++v)
                up[k][v] = up[k - 1][up[k - 1][v]];
    }

    int query(int u, int v) const {
        if (depth[u] < depth[v]) swap(u, v);
        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; ++k)
            if (diff >> k & 1) u = up[k][u];
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; --k)
            if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
        return up[0][u];
    }
};

The root's parent is set to the root itself, so jumps past the top stay at the root and never index out of bounds. Preprocessing is O(n log n) time and space; each query is O(log n). It also answers "k-th ancestor of a node" (LeetCode 1483) and path queries like distance between two nodes: depth[u] + depth[v] - 2 * depth[lca].

In a standard SDE interview, mentioning binary lifting and sketching the two phases is usually enough; full code is more common in competitive programming and some online assessments. The Euler tour approach reduces LCA to range minimum query, a technique covered alongside sparse tables and segment trees in segment trees and Fenwick trees explained, and Tarjan's method uses union-find.

Interview Strategy and Common Mistakes

A strong presentation of LC 236 takes about ten minutes:

1. Clarify. Is it a BST? Are both nodes guaranteed to exist? Do nodes have parent pointers? Can a node be its own ancestor? Each answer selects a different variant, and asking shows you know they exist.
2. Mention the path approach in one sentence, then propose the single-pass recursion.
3. State the contract of the function before coding: both found returns LCA, one found returns that node, none returns null.
4. Code the six lines.
5. Dry run two cases: a split case like (7, 4) and an ancestor case like (5, 4).
6. Complexity: O(n) time, O(h) space. Name the skewed-tree recursion risk.

Mistakes I see in mock interviews

• Not handling the ancestor case. Candidates add extra checks to "make sure" q is below p. Unnecessary under the problem guarantee, and it hints at not understanding the contract.
• Using the BST algorithm on a general binary tree. Comparing values is meaningless without the BST property.
• Using the general algorithm on a BST. Correct but wastes the O(h) solution.
• Claiming the short-circuit version works when nodes may be missing. It returns p even if q does not exist.
• Comparing by value when the interviewer has said values may repeat.

Follow-ups that build on LCA

• Distance between two nodes: depth(p) + depth(q) − 2 · depth(LCA).
• LCA of deepest leaves (LeetCode 1123): return (depth, node) pairs from each subtree.
• Path between two nodes: path from p up to the LCA, then down to q.
• LCA in an N-ary tree or a DAG: the N-ary version counts how many children returned non-null; a DAG can have several "lowest" common ancestors, so ask how to define the answer.

The same "decide what each node returns to its parent" pattern powers diameter, maximum path sum and balanced-tree checks; practise them together in binary tree interview problems. If recursion contracts still feel slippery, start with recursion for beginners, then try LeetCode 297 Serialize and Deserialize Binary Tree as the next tree hard.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.