MediumFind the deepest node that has both target nodes as descendants.
Given the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA): the deepest node that has both p and q as descendants. A node may be a descendant of itself.
Walkthrough
presets:
LeetCode array format · p and q are node values
1
function lca(root, p, q) {
◄
2
if (!root) return null;
3
if (root.val === p || root.val === q) return root;
4
const left = lca(root.left, p, q);
5
const right = lca(root.right, p, q);
6
if (left && right) return root;
7
return left || right;
8
}
call stack (root → current)
—
p / qvisitingcontains a targetLCA
STEP 0 / 7 · line 1
Start
Find the lowest common ancestor of 5 and 1. Each call reports whether a target lives in its subtree.
Intuition
Solve it bottom-up: ask each node “does my subtree contain p or q?”
A call returns a non-null signal if a target is found at or below that node.
If a node hears back from BOTH its left and right subtrees, the two targets first meet here — this node is the LCA.
If only one side reports a target, pass that signal straight up; the meeting point is higher.
The algorithm
01If the node is null or is one of the targets, return it.
02Recurse into the left and right children.
03If both recursive calls return non-null, the current node is the LCA.
04Otherwise return whichever side was non-null (or null if neither).
Reference implementations
1 · Recursive — works on any binary tree
Bottom-up DFS: each call reports whether a target is in its subtree; the node that hears back from both sides is the LCA.
1
function lowestCommonAncestor(root, p, q) {
2
if (!root || root === p || root === q) return root;
3
const left = lowestCommonAncestor(root.left, p, q);
4
const right = lowestCommonAncestor(root.right, p, q);
5
if (left && right) return root;
6
return left || right;
7
}
2 · Iterative — binary search tree only
When the tree is a BST, the ordering tells you which way to walk. Where the paths to p and q diverge is the LCA — O(h) time, O(1) space.