Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
There's no BST ordering to exploit here, so you can't compare values — you must search. Do a single post-order DFS that returns a node if the subtree rooted there contains p or q (or is p/q itself). At each node, look at what the left and right subtrees reported: if BOTH came back non-null, the two targets are on opposite sides, so THIS node is the LCA. If only one side reported a target, bubble that result up. The first node where the two searches converge is the answer.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you realize that without BST ordering you must search both subtrees, and whether you express the answer as a post-order aggregation: the node where left and right searches both succeed is the LCA.
Where candidates slip
Trying to compare p.val and q.val against node.val (only valid for a BST), or returning too early / mishandling the case where one target is an ancestor of the other (p inside q's subtree).
How to stand out
State the post-order contract precisely — 'each call returns p, q, the LCA, or null' — and explain why returning the node itself in the base case correctly handles the ancestor-of-itself case without special-casing it.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewAt node: get left and right search resultsnode == p or q, or null?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Single Post-Order DFS (Optimal)
1Hint 1Explore hintHide hint
There's no value ordering to exploit, so you can't decide which way to go by comparing — you must look in both subtrees. What should a recursive call tell its parent?
2Hint 2Explore hintHide hint
Make each call return: the node if it IS p or q, otherwise whatever its subtrees found. Think about what it means when both the left and right calls come back non-null.
3Hint 3Explore hintHide hint
If left and right both return something, p and q are on opposite sides, so the current node is their lowest common ancestor. If only one side returns a node, pass it up — the answer is at or above it.
A · Core idea
Without a BST's ordering we cannot decide which direction p or q lies by comparing values, so the algorithm is fundamentally a search of both subtrees combined with a clever return contract. The contract is the heart of it: each recursive call returns a node that 'represents' what was found in its subtree — either p, q, the LCA itself if already determined, or null if neither target is present below.
Why the base case returns the node on a match. When we hit null we return null (nothing here). When we hit p or q we return that node — even without checking whether the other target is below it. This is the move that elegantly handles 'a node is an ancestor of itself'. Suppose p is an ancestor of q. The DFS reaches p and immediately returns p. Higher up, the side containing p reports p, the other side reports null, so we propagate p upward — and since q lives beneath p, no node above ever sees a second non-null sibling, so p correctly emerges as the answer.
Why 'both sides non-null' identifies the LCA. After recursing, examine left and right. If both are non-null, then one target was found somewhere in the left subtree and the other in the right subtree. The only node that has p in one subtree and q in the other is precisely the node where their root-to-node paths diverge — by definition the lowest common ancestor. So we return the current node, and because we're unwinding post-order (bottom-up), the first (lowest) such split point is the one that gets locked in; nodes above it will only ever see this single result on one side.
Why one-sided results bubble up unchanged. If only left is non-null, every target found so far lives in the left subtree, so the answer is at or above the node left points to — we return left untouched. Symmetrically for right. If both are null, neither target is below, so we return null. This propagation is what carries the eventual answer all the way up to the root without re-deriving it.
Why post-order is mandatory. We must know what both subtrees found before we can decide anything at the current node — a pre-order decision would be premature because we haven't searched below yet. Gathering left and right first, then deciding, is the textbook post-order shape, and it's why this whole family of problems (subtree aggregation, diameter, balanced check) shares the same skeleton.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1Interactive diagram
Searching for LCA(5, 1) in the example tree
lca(6),lca(2)5 is found in the left subtree, 1 in the right subtree of 3 — both non-null at node 3, so 3 is the LCA.
3C · Code with teaching comments
D · Why it works and complexityO(n) timeO(h) spaceOpen the invariant and proofExplore the proofHide the proof
The single trick is overloading the return value: a non-null return means 'a target (or the LCA) lives in or below me'. The unique node that receives a non-null report from BOTH children is where p and q's paths split — and post-order guarantees we detect the lowest such node first. No parent pointers, no second pass, one O(n) sweep.
ComplexityO(n) time, O(h) space — A single DFS visits each node once with O(1) work per node → O(n) time. Recursion depth equals the tree height h → O(h) stack space, O(log n) balanced and O(n) degenerate.
E · Edge cases and pitfalls7p = 5, q = 4 (q under p) — DFS hits 5, returns 5 immediately; 4 lives below but is never separately reported above 5, so 5 propagates up as the LCA — the ancestor-of-itself case.Explore edge casesHide edge cases
Edge cases handled
p = 5, q = 4 (q under p)DFS hits 5, returns 5 immediately; 4 lives below but is never separately reported above 5, so 5 propagates up as the LCA — the ancestor-of-itself case.p and q are the two children of the rootleft returns p, right returns q → both non-null at root → root is the LCA.Degenerate (linked-list) treeRecursion depth is O(n); the deeper of p/q is found first and bubbles up as the LCA since the other is its ancestor.
Pitfalls
- Comparing p.val/q.val with node.val as if it were a BST — invalid ordering in a general tree.
- Forgetting that a node can be its own ancestor, then special-casing it incorrectly.
- Stopping the search at the first target without searching the other subtree — breaks the both-sides test.
- Using == on values instead of node identity when duplicate-looking nodes exist (values are unique here, but identity is the safe habit).
Approach 2 of 2
Parent-Pointer Mapping + Ancestor-Set Intersection
1Hint 1Explore hintHide hint
If you knew each node's parent, finding the LCA would be like finding where two paths to the root meet.
2Hint 2Explore hintHide hint
First DFS/BFS the tree recording each node's parent in a map. Then walk from p up to the root, storing every ancestor in a set.
3Hint 3Explore hintHide hint
Now walk from q upward; the first ancestor already in p's set is the lowest common ancestor.
A · Core idea
This approach reduces LCA to the classic 'intersection of two upward paths' problem by first manufacturing the parent links the tree doesn't natively provide. It's especially natural when the node type does carry a parent pointer.
Step one: record parents. A single traversal from the root builds a map child → parent. We stop early once both p and q have been assigned parents, since we only need the ancestor chains of those two nodes, but building the full map is also fine and keeps the code simple.
Step two: collect p's ancestor chain. Starting at p, repeatedly hop to the parent, inserting each node into a set, until we pass the root. This set is exactly the set of nodes on the path from p up to and including the root — every node that is an ancestor of p (counting p itself).
Step three: walk q up until we hit that set. Now climb from q toward the root. The first node we encounter that is already in p's ancestor set is, by construction, an ancestor of both p and q. Because we climb from q and stop at the very first hit, it is also the lowest such common ancestor — any higher common ancestor would be encountered later. That first intersection is the LCA.
Why this is essentially the linked-list-intersection trick. Each node's chain of parents up to the root is a linked list, and two such lists share a common suffix (the path from the LCA to the root). Finding the LCA is finding the start of that shared suffix — identical in spirit to finding where two linked lists merge. The trade-off versus the single-DFS solution is explicit O(n) space for the parent map and ancestor set, in exchange for a more mechanical, two-phase structure that some find easier to reason about and that generalizes when parent pointers are already present.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
root = [3,5,1,6,2,0,8,null,null,7,4], p = 7, q = 4parents
map: 7→2, 4→2, 2→5, 5→3, 1→3, ...
parent map built2C · Code with teaching comments
Reference implementation previewpublic TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Map<TreeNode, TreeNode> parent = new HashMap<>(); parent.put(root, null); Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root);Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
LCA equals the first meeting point of the two upward paths to the root. Once you see each node's ancestor chain as a linked list sharing a common tail, this becomes the same problem as intersection of two linked lists — a satisfying cross-pattern connection worth mentioning.
ComplexityO(n) time, O(n) space — Building the parent map visits every node once → O(n). Collecting p's ancestors is O(h), and walking q upward is O(h). Storage for the parent map and ancestor set is O(n).
E · Edge cases and pitfalls7p is the root — p's ancestor set contains only the root; climbing q reaches the root eventually → LCA is the root (p itself).Explore edge casesHide edge cases
Edge cases handled
p is the rootp's ancestor set contains only the root; climbing q reaches the root eventually → LCA is the root (p itself).p ancestor of qClimbing from q passes through p, which is in p's own ancestor set → returns p.Wide treeParent map is O(n) space but height is small, so the two upward walks are short.
Pitfalls
- Forgetting to add p itself to its ancestor set, missing the ancestor-of-itself case.
- Looping forever if the parent map is incomplete (didn't traverse far enough).
- Using O(n) space when the single-DFS solution needs only O(h) — call out the trade-off.
- Comparing by value instead of node identity when populating the maps.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code preview// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Using BST value comparison on a general tree
LCA of a BST navigates by comparing values, but a general binary tree has no ordering. Comparing node.val to p.val/q.val sends you down the wrong branch.
Explore the code comparisonHide the code comparison
Using BST value comparison on a general tree
LCA of a BST navigates by comparing values, but a general binary tree has no ordering. Comparing node.val to p.val/q.val sends you down the wrong branch.
Don't write this
if (p.val < root.val && q.val < root.val)
return lowestCommonAncestor(root.left, p, q); // only valid for a BST!
if (p.val > root.val && q.val > root.val)
return lowestCommonAncestor(root.right, p, q);Write this instead
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;2Mishandling ancestor-of-itself
If you require BOTH subtrees to confirm a target before returning a node, you miss the case where q lives under p — p should win, but the over-strict check returns null.
Explore the code comparisonHide the code comparison
Mishandling ancestor-of-itself
If you require BOTH subtrees to confirm a target before returning a node, you miss the case where q lives under p — p should win, but the over-strict check returns null.
Don't write this
def lca(node, p, q):
if node is None:
return None
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right:
return node
# bug: never checks if node itself is p or q
return left or rightWrite this instead
def lca(node, p, q):
if node is None or node is p or node is q:
return node
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right:
return node
return left if left is not None else right3Deciding pre-order before subtree results exist
The both-sides test requires knowing what each subtree found. Returning the current node before recursing into both children produces wrong answers because you haven't located the targets yet.
Explore the code comparisonHide the code comparison
Deciding pre-order before subtree results exist
The both-sides test requires knowing what each subtree found. Returning the current node before recursing into both children produces wrong answers because you haven't located the targets yet.
Don't write this
if (root == p || root == q) return root;
if (lowestCommonAncestor(root.left, p, q) != null) return root; // premature: subtrees not both searchedWrite this instead
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;Revise
Carry the pattern into the interview
Pattern to remember
Post-order DFS that bubbles up p/q sightings; split point is the LCA
Code pattern to memorize
lca(node, p, q):
if node is null or node == p or node == q: return node
left = lca(node.left, p, q)
right = lca(node.right, p, q)
if left and right: return node # p and q split here → LCA
return left != null ? left : right # both on one side (or none)Rules to remember
- 1This is a plain binary tree — no value ordering, so you must search both subtrees, not navigate by comparison.
- 2Base case returns the node itself when it equals p or q — a node can be its own ancestor.
- 3If both children return non-null, the current node is the split point → it's the LCA.
- 4If only one side returns non-null, propagate that result upward — the LCA is higher or is that returned node.
- 5Recurse post-order: gather left and right answers before deciding at the current node.
Use this pattern when
- Find the lowest node that is an ancestor of two given nodes in an UNORDERED binary tree
- Both p and q are guaranteed to exist in the tree
- A node may be an ancestor of itself (p is an ancestor of q)
- You want a single O(n) pass without parent pointers
Choose another pattern when
- Tree is a BST → compare values to walk down in O(h) (LCA of a BST)
- Nodes have parent pointers → walk up and intersect the two ancestor chains
- p or q might NOT exist → you must verify presence, changing the return contract
- Many repeated queries on a static tree → preprocess with binary lifting / Euler tour + RMQ
Interview takeaway
LCA in a general binary tree is the canonical 'bubble-up a sighting' post-order: each node reports whether a target lives below it, and the unique node that hears 'yes' from both sides is where the paths to p and q diverge. Master this and you've mastered the post-order aggregation pattern.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternPost-order aggregation that bubbles a 'sighting' upward. Recognise it whenever the answer depends on information from both subtrees combined at the node above them. The same shape — recurse both sides, then decide — powers Diameter of Binary Tree, Balanced Binary Tree, and Binary Tree Maximum Path Sum.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Lowest Common Ancestor of a Binary Search TreeBST ordering lets you walk down by comparing values — O(h) and no recursion needed.
- Lowest Common Ancestor of a Binary Tree IIIComing soonNodes have parent pointers — turn it into linked-list intersection.
- Lowest Common Ancestor of a Binary Tree IIComing soonp or q may NOT exist — track found-counts so you only return a real common ancestor.
- Lowest Common Ancestor of Deepest LeavesComing soonReturn both a depth and the candidate LCA in one post-order pass.