Lowest Common Ancestor of a Binary Tree (LeetCode 236)
You're given an ordinary binary tree (no BST ordering to lean on) and two of its nodes, p and q. Find their lowest common ancestor (LCA): the deepest node that still has both of them somewhere in its subtree.
A node counts as its own descendant, so if p sits directly above q, p itself is the answer.
Worked Examples
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 45root = [1,2], p = 1, q = 211 is the parent of 2, and a node counts as its own descendant, so the answer is 1.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[2, 105].-109 <= Node.val <= 109All
Node.valare unique.p != qpandqwill exist in the tree.
Core Insight
Bifurcation detection in post-order traversal identifies the unique meeting point of two search targets.
Real-World Scenario & Production Applications
Version control merge-base commit identification (git merge-base), DOM event bubbling ancestor resolution.
Subproblems & Recurrence Decomposition3 Phases
If the current node is null, or IS one of p/q, it can't recurse further meaningfully -- return the node itself as a candidate signal.
if not node or node == p or node == q:
return nodeStep-by-Step Execution Trace Table
| Node | Left Result | Right Result | Combined Result |
|---|---|---|---|
| 5 | Node 5 | None | Returns Node 5 |
| 1 | None | Node 1 | Returns Node 1 |
| 3 (root) | Node 5 | Node 1 | Both non-null -> Return Node 3 (LCA) |
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13| Node | Left Result | Right Result | Combined Result |
|---|---|---|---|
| 5 | Node 5 | None | Returns Node 5 |
| 1 | None | Node 1 | Returns Node 1 |
| 3 (root) | Node 5 | Node 1 | Both non-null -> Return Node 3 (LCA) |
| 1 | if not root or root == p or root == q: |
| 2 | return root |
| 3 | left = lowestCommonAncestor(root.left, p, q) |
| 4 | right = lowestCommonAncestor(root.right, p, q) |
| 5 | if left and right: |
| 6 | return root |
| 7 | return left if left else right |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Without a BST's ordering to guide the search, you can no longer pick a single direction to walk (the BST-LCA trick doesn't apply) — you genuinely have to search both subtrees. The insight is in how each side reports back.
🎉 The Analogy: Two Search Parties Reporting to a Reunion Coordinator
Imagine you're coordinating a family reunion, trying to find the first shared ancestor of two relatives, p and q. You send one search party down the left branch and one down the right, each with the same instructions: "come back and tell me if you found p or q (or both) anywhere down there." If your left party comes back having found someone and your right party also comes back having found someone, you now know: one relative is on the left, the other is on the right — which makes you the first point where their family lines converge, the LCA. If only one party found anyone, you don't know anything definitive yet — you just relay whoever they found upward, letting your own parent keep asking the same question.
🔑 The Key Idea in the Code
Finding the node itself (node == p or node == q) short-circuits the search on that branch immediately — you don't need to keep digging once you've found one of the two targets, because a node is considered its own ancestor.
Over-searching after finding target: When
root == p or root == q, you can returnrootimmediately; you do not need to search beneath it because whether the other target is in its subtree or not,rootis the LCA or candidate.Conflating return values: If both left and right return non-null,
rootis the LCA. If only one returns non-null, propagate that non-null node upward. ReturningNonewhen one child found target loses the candidate.Assuming node values are unique across trees: Always compare node object references (
root == p), not.val, in general tree implementations.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
LCA query on an arbitrary binary tree without BST ordering.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a subtree returns a non-null node if and only if it contains p or q.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use post-order divide and conquer. If root is None or matches p or q, I return root. I search left and right subtrees. If both return non-null, root is the LCA. If only one returns non-null, I return that child. Runs in
O(N)time and O(H) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Post-order DFS visits every node once. Returns node if matches p or q; if left and right child calls both return non-null, current node is LCA. Single pass.
O(H) Auxiliary
Call stack reaches maximum depth equal to tree height H.
T(N) = 2T(N/2) + O(1) = O(N)
Derivation Progression
L = LCA(v.left), R = LCA(v.right)
Recursively searches both subtrees in O(1) per node.
if L and R: return v
If both children report a target, current node is the lowest common ancestor.
N nodes = O(N)
Examines each tree node exactly once.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack frames (H in [log N, N])
O(1) Zero heap memory
O(1) Node reference
Boundary Best / Worst Cases
if root is p or q.
.
if p and q are deep leaves.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "lowest common ancestor in a binary tree". In a general binary tree without BST ordering, values provide no directional hints. A Senior SWE uses Bottom-Up Post-Order Bifurcation Search: return a pointer to or if found in the subtree; if both left and right subtrees return non-null pointers, current node is the bifurcation point (LCA)!
. Time budget is strictly single pass.
One target is ancestor of the other (e.g. is ancestor of ): the base case if root == p or root == q: return root immediately returns without searching deeper, which is correct because is indeed the LCA.
Lowest Common Ancestor of a Binary Tree (LeetCode 236)
You're given an ordinary binary tree (no BST ordering to lean on) and two of its nodes, p and q. Find their lowest common ancestor (LCA): the deepest node that still has both of them somewhere in its subtree.
A node counts as its own descendant, so if p sits directly above q, p itself is the answer.
Worked Examples
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 45root = [1,2], p = 1, q = 211 is the parent of 2, and a node counts as its own descendant, so the answer is 1.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[2, 105].-109 <= Node.val <= 109All
Node.valare unique.p != qpandqwill exist in the tree.
Core Insight
Bifurcation detection in post-order traversal identifies the unique meeting point of two search targets.
Real-World Scenario & Production Applications
Version control merge-base commit identification (git merge-base), DOM event bubbling ancestor resolution.
Subproblems & Recurrence Decomposition3 Phases
If the current node is null, or IS one of p/q, it can't recurse further meaningfully -- return the node itself as a candidate signal.
if not node or node == p or node == q:
return nodeStep-by-Step Execution Trace Table
| Node | Left Result | Right Result | Combined Result |
|---|---|---|---|
| 5 | Node 5 | None | Returns Node 5 |
| 1 | None | Node 1 | Returns Node 1 |
| 3 (root) | Node 5 | Node 1 | Both non-null -> Return Node 3 (LCA) |
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 13| Node | Left Result | Right Result | Combined Result |
|---|---|---|---|
| 5 | Node 5 | None | Returns Node 5 |
| 1 | None | Node 1 | Returns Node 1 |
| 3 (root) | Node 5 | Node 1 | Both non-null -> Return Node 3 (LCA) |
| 1 | if not root or root == p or root == q: |
| 2 | return root |
| 3 | left = lowestCommonAncestor(root.left, p, q) |
| 4 | right = lowestCommonAncestor(root.right, p, q) |
| 5 | if left and right: |
| 6 | return root |
| 7 | return left if left else right |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Without a BST's ordering to guide the search, you can no longer pick a single direction to walk (the BST-LCA trick doesn't apply) — you genuinely have to search both subtrees. The insight is in how each side reports back.
🎉 The Analogy: Two Search Parties Reporting to a Reunion Coordinator
Imagine you're coordinating a family reunion, trying to find the first shared ancestor of two relatives, p and q. You send one search party down the left branch and one down the right, each with the same instructions: "come back and tell me if you found p or q (or both) anywhere down there." If your left party comes back having found someone and your right party also comes back having found someone, you now know: one relative is on the left, the other is on the right — which makes you the first point where their family lines converge, the LCA. If only one party found anyone, you don't know anything definitive yet — you just relay whoever they found upward, letting your own parent keep asking the same question.
🔑 The Key Idea in the Code
Finding the node itself (node == p or node == q) short-circuits the search on that branch immediately — you don't need to keep digging once you've found one of the two targets, because a node is considered its own ancestor.
Over-searching after finding target: When
root == p or root == q, you can returnrootimmediately; you do not need to search beneath it because whether the other target is in its subtree or not,rootis the LCA or candidate.Conflating return values: If both left and right return non-null,
rootis the LCA. If only one returns non-null, propagate that non-null node upward. ReturningNonewhen one child found target loses the candidate.Assuming node values are unique across trees: Always compare node object references (
root == p), not.val, in general tree implementations.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
LCA query on an arbitrary binary tree without BST ordering.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a subtree returns a non-null node if and only if it contains p or q.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use post-order divide and conquer. If root is None or matches p or q, I return root. I search left and right subtrees. If both return non-null, root is the LCA. If only one returns non-null, I return that child. Runs in
O(N)time and O(H) space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Post-order DFS visits every node once. Returns node if matches p or q; if left and right child calls both return non-null, current node is LCA. Single pass.
O(H) Auxiliary
Call stack reaches maximum depth equal to tree height H.
T(N) = 2T(N/2) + O(1) = O(N)
Derivation Progression
L = LCA(v.left), R = LCA(v.right)
Recursively searches both subtrees in O(1) per node.
if L and R: return v
If both children report a target, current node is the lowest common ancestor.
N nodes = O(N)
Examines each tree node exactly once.
Variable Definitions
Total number of nodes in the binary tree
Tree height (log N in balanced tree, N in skewed tree)
Memory Architecture & Bounds
O(H) Call stack frames (H in [log N, N])
O(1) Zero heap memory
O(1) Node reference
Boundary Best / Worst Cases
if root is p or q.
.
if p and q are deep leaves.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "lowest common ancestor in a binary tree". In a general binary tree without BST ordering, values provide no directional hints. A Senior SWE uses Bottom-Up Post-Order Bifurcation Search: return a pointer to or if found in the subtree; if both left and right subtrees return non-null pointers, current node is the bifurcation point (LCA)!
. Time budget is strictly single pass.
One target is ancestor of the other (e.g. is ancestor of ): the base case if root == p or root == q: return root immediately returns without searching deeper, which is correct because is indeed the LCA.