Trees · LC #236
Lowest Common Ancestor
Find the lowest node in a binary tree that has both p and q as descendants. Post-order DFS propagates found-node signals upward - the first node receiving non-null from both sides is the LCA.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). The LCA is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).
Sample I/O
Input: tree=[3,5,1,6,2,0,8,null,null,7,4], p=5, q=1 Output: 3 Input: same tree, p=5, q=4 Output: 5 (5 is ancestor of itself)
Time: O(n) · Space: O(h)
Intuition
How to Think About It
Intuition
Post-order DFS works because by the time we process a node, we already know what its subtrees contain. If both left and right return non-null, p and q are on different sides - current node is the LCA. If only one side returns, both nodes are in that subtree and the LCA is deeper.
Core Concept
Base cases: null → null; node == p or node == q → return that node. Recurse left and right. If both non-null → return root (split point = LCA). If only one non-null → return that one (LCA is in that subtree). This elegantly handles the case where p is an ancestor of q.
When to use
LCA queries on general binary trees, path problems, distance between nodes, hierarchical relationship queries.
When NOT to use
For BSTs, use the BST-specific LCA (LC 235) which is O(h) without full traversal. If many LCA queries on same tree, use preprocessing with sparse table (O(n log n) build, O(1) query).
Key Insights
What to Know Cold
- "Both non-null" condition means p and q found on opposite sides - current node is the answer.
- "Only one non-null" means both p and q are in the same subtree - LCA was found deeper.
- A node can be its own ancestor - base case `root == p || root == q` returns early.
- The function returns the LCA once found and propagates it upward unchanged.
- Assumes both p and q are guaranteed to exist in the tree.
2 examples
Worked Examples
Split-point LCA
p=5 (left subtree), q=1 (right subtree) - LCA is root 3.
DFS from 3: left returns 5 (found p), right returns 1 (found q). Both non-null → return 3.
function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
if (!root || 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;
}Output: Node 3
The "both non-null" branch is the key insight for general binary trees.
Ancestor is one of the nodes
p=5, q=4 where 4 is in subtree of 5 - LCA is 5.
DFS hits node 5 before finding q=4. Returns 5 immediately. Right subtree never contains p/q → returns null. Only left returns non-null (5) → propagates 5 upward.
Output: Node 5
The "node can be its own ancestor" rule handled by early return base case.