Lowest Common Ancestor of a Binary Tree — LC 236 Post-Order DFS Interview Guide

Problem Statement#

Given a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the lowest node that has both p and q as descendants, where a node can be a descendant of itself.

Constraints:

• Number of nodes is in range 2 to 100000
• Node values are unique and in range -1000000000 to 1000000000
• Both p and q exist in the tree
• p is not equal to q

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5

Why This Problem Matters#

LeetCode 236 Lowest Common Ancestor of a Binary Tree is one of the most asked Medium tree problems at Amazon, Meta, Google, Apple, Microsoft, and Bloomberg. It is the gateway problem to post-order propagation — a recursion pattern where each call reports back what it found, and parents combine those reports to make decisions.

The problem also tests whether candidates correctly handle the "ancestor case" where one of the targets is an ancestor of the other. The clean trick — return the matching node immediately on first contact — handles this case automatically without any special-case branching.

For senior loops, the follow-ups extend in two directions: BST-specific O(h) navigation (LC 235), and LCA with parent pointers (LC 1650). Mastering the post-order template makes related problems like distance between two nodes, kth ancestor, and binary tree maximum path sum easier to derive.

The Core Insight#

Post-order DFS visits both subtrees before deciding what the current node should return. The recursive function lca(node, p, q) returns:

• null if neither p nor q is in the subtree rooted at node.
• p or q if exactly one of them is in this subtree (acting as a "found" marker that propagates upward).
• The LCA itself, once found, propagates upward.

The decision at each node:

1. If node itself equals p or q, return node immediately. No need to descend further — if the other target is below, the current node is the LCA.
2. Recurse into both children. If both return non-null, this node is the split point — return node.
3. Otherwise, return whichever side returned non-null (or null if both were null).

The "return on first match" rule elegantly handles the ancestor case.

Visual Dry Run#

Tree: 3 -> {5 -> {6, 2 -> {7, 4}}, 1 -> {0, 8}}, p = 5, q = 1.

The split happens at node 3 because 5 came up from the left and 1 came up from the right.

Solution (Optimal)#

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if not root:
            return None
        if root == p or root == 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 if left else right

var lowestCommonAncestor = function(root, p, q) {
    if (!root) return null;
    if (root === p || root === q) return root;
 
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
 
    if (left && right) return root;
    return left || right;
};

Time: O(n) — every node is visited at most once. Space: O(h) — recursion stack proportional to tree height; O(log n) balanced, O(n) skewed.

Common Mistakes#

• Using BST navigation (compare values, go left or right) on a generic binary tree — only works for LC 235
• Continuing to recurse into a subtree of a target node — wastes work; returning immediately is correct and simpler
• Comparing nodes by value instead of by identity — fails the moment duplicates appear (this problem says unique, but the habit is wrong)
• Returning null when only one side is non-null — must propagate the non-null result up
• Confusing post-order (decide after recursion) with pre-order (decide before) — pre-order cannot detect splits

Interview Tips#

• Explicitly call out the ancestor case before coding: "if p is ancestor of q, returning p on first match is correct because the algorithm will not find q again"
• Walk through both example pairs (5,1 split at 3; and 5,4 ancestor at 5) on the whiteboard
• Mention LC 235 (LCA in BST) as the BST-optimized variant with O(h) time and O(1) space
• For follow-ups with frequent queries, mention binary lifting precompute for O(log n) per query

Follow-up Questions#

• LCA in a BST (LC 235) — exploit ordering, walk down without recursion
• Distance between two nodes — depth(p) + depth(q) - 2 * depth(LCA)
• LCA with parent pointers (LC 1650) — two-pointer approach, no tree walk needed
• Binary lifting for repeated LCA queries — O(n log n) preprocess, O(log n) per query

Key Takeaways#

• LeetCode 236 LCA of a Binary Tree is Medium and a top-tier post-order DFS problem at Amazon, Meta, Google, Apple, and Microsoft
• Time is O(n); space is O(h) for the recursion stack
• Pattern: return matching node on first contact; otherwise propagate non-null subtree result, return current node when both sides return non-null
• The "return immediately on match" rule handles the ancestor case without special branching
• Compare nodes by reference (root == p), not by value, to stay safe across variants
• Same template extends to distance between nodes, binary tree max path sum, and diameter
• For BSTs use LC 235's O(h) navigation; do not waste the BST property on this generic algorithm