Path Sum II (LeetCode 113)
You're given the root of a binary tree and a target number targetSum. Collect every root-to-leaf path whose node values add up to targetSum, with each path reported as a plain list of values (not node objects).
A root-to-leaf path always starts at the root and ends at a leaf — a node with no children at all.
Worked Examples
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22[[5,4,11,2],[5,8,4,5]]root = [1,2,3], targetSum = 5[]3 and 4; neither is 5.root = [1,2], targetSum = 0[]1 -> 2, sums to 3, not 0.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Core Insight
Sharing a single path buffer and reverting it with path.pop() reduces memory from O(N^2) to O(H) auxiliary space.
Real-World Scenario & Production Applications
Rule-engine execution traces, financial ledger audit trail verification, and decision-tree classification paths.
Subproblems & Recurrence Decomposition3 Phases
Carry the accumulated sum and the current root-to-node path as recursion parameters; append the current node's value to the path before recursing into children.
path.append(node.val)
remaining = targetSum - node.valStep-by-Step Execution Trace Table
| Call Frame | Node Visited | Active Path Buffer path | Running Remaining Sum remain | Leaf Check (not left and not right) | Action / Backtrack Status |
|---|---|---|---|---|---|
| 1 | 5 (root) | [5] | False | Recurse left child 4 | |
| 2 | 4 | [5, 4] | False | Recurse left child 11 | |
| 3 | 11 | [5, 4, 11] | False | Recurse left child 7 | |
| 4 | 7 | [5, 4, 11, 7] | True (Leaf) | Remain $ | |
eq 0 ⟹$ no match. Backtrack: path.pop() -> 7 | |||||
| 5 | 2 | [5, 4, 11, 2] | True (Leaf) | Target matched! Snapshot results.append([5, 4, 11, 2]). Backtrack: path.pop() -> 2 | |
| - | - | [5, 4] | 13 | - | Backtrack from 11 (path.pop() -> 11), then backtrack from 4 (path.pop() -> 4) |
| 6 | 8 | [5, 8] | False | Recurse left child 13 | |
| 7 | 13 | [5, 8, 13] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 13 | |||||
| 8 | 4 | [5, 8, 4] | False | Recurse left child 5 | |
| 9 | 5 | [5, 8, 4, 5] | True (Leaf) | Target matched! Snapshot results.append([5, 8, 4, 5]). Backtrack: path.pop() -> 5 | |
| 10 | 1 | [5, 8, 4, 1] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 1 | |||||
| - | - | [] | 22 | - | Search completes; return [[5, 4, 11, 2], [5, 8, 4, 5]] |
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22[[5,4,11,2],[5,8,4,5]]| Call Frame | Node Visited | Active Path Buffer path | Running Remaining Sum remain | Leaf Check (not left and not right) | Action / Backtrack Status |
|---|---|---|---|---|---|
| 1 | 5 (root) | [5] | False | Recurse left child 4 | |
| 2 | 4 | [5, 4] | False | Recurse left child 11 | |
| 3 | 11 | [5, 4, 11] | False | Recurse left child 7 | |
| 4 | 7 | [5, 4, 11, 7] | True (Leaf) | Remain $ | |
eq 0 ⟹$ no match. Backtrack: path.pop() -> 7 | |||||
| 5 | 2 | [5, 4, 11, 2] | True (Leaf) | Target matched! Snapshot results.append([5, 4, 11, 2]). Backtrack: path.pop() -> 2 | |
| - | - | [5, 4] | 13 | - | Backtrack from 11 (path.pop() -> 11), then backtrack from 4 (path.pop() -> 4) |
| 6 | 8 | [5, 8] | False | Recurse left child 13 | |
| 7 | 13 | [5, 8, 13] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 13 | |||||
| 8 | 4 | [5, 8, 4] | False | Recurse left child 5 | |
| 9 | 5 | [5, 8, 4, 5] | True (Leaf) | Target matched! Snapshot results.append([5, 8, 4, 5]). Backtrack: path.pop() -> 5 | |
| 10 | 1 | [5, 8, 4, 1] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 1 | |||||
| - | - | [] | 22 | - | Search completes; return [[5, 4, 11, 2], [5, 8, 4, 5]] |
| 1 | results: List[List[int]] = [] |
| 2 | path: List[int] = [] |
| 3 | def dfs(node, rem): |
| 4 | if not node: |
| 5 | return |
| 6 | path.append(node.val) |
| 7 | if not node.left and not node.right and rem == node.val: |
| 8 | results.append(list(path)) |
| 9 | dfs(node.left, rem - node.val) |
| 10 | dfs(node.right, rem - node.val) |
| 11 | path.pop() |
| 12 | dfs(root, targetSum) |
| 13 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every earlier DFS archetype in this pattern only returned a value upward. This one needs to return the actual route taken — and reusing one shared list for every branch requires cleaning up after yourself.
🧭 The Analogy: A Tour Guide's Reusable Clipboard
Imagine a tour guide leading groups down every possible branching trail from a starting point, using a single shared clipboard to jot down each stop as they walk. When the group reaches a destination that satisfies the goal (a leaf whose path sums to the target), the guide photographs the clipboard as it currently stands — a snapshot of this one specific route. But before backtracking to try a different branch, the guide erases the last entry they wrote. Why? Because the next branch they explore needs the clipboard to look exactly like it did before this branch was ever tried — otherwise leftover entries from an abandoned route would contaminate every future path.
🔑 The Key Idea in the Code
results.append(list(path)) (a copy) versus results.append(path) (a reference) is the detail that silently breaks this pattern the first time most people write it — without the copy, every recorded "answer" points at the same list object, which keeps changing, and they'd all end up empty by the time the recursion finishes.
Appending mutable path reference to results: Appending
pathinstead of a snapshot copypath[:]orlist(path)results in an output full of empty lists after backtracking pops.Evaluating target sum at non-leaf nodes: Triggering answer collection when
remaining == 0without verifyingnot node.left and not node.rightcounts internal prefix paths that don't terminate at a leaf.Backtrack popping in base case: If you pop inside an early return branch for
node is None, you double-pop parent nodes. Maintain symmetry: append on entry, pop on exit.Early exit with negative numbers: Pruning search when
remaining < 0fails when negative numbers exist later in the tree.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for every root-to-leaf path whose values add up to targetSum, returned as the lists of values themselves: whole paths must be listed, not just counted, which is the Root-to-Leaf Paths signal.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
At each node: path.append(node.val); if the node is a leaf and rem == node.val, save list(path); recurse on both children with rem - node.val; then path.pop().
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: pop after both children, even when the node matched.
Values and
targetSumcan be negative, so never stop a branch early because its running sum has passed the target: on[-2,null,-3]withtargetSum = -5, the answer needs both nodes.A path holds at least one node: an empty tree returns
[]even whentargetSum = 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Root-to-Leaf Paths. I keep one shared list, path, that always holds exactly the nodes from the root to where I am, plus rem, what the path still needs, starting at targetSum. At each node I append its value. If it's a leaf and rem equals its value, the path works, so I save a copy of the list, because the shared list keeps changing after I return. Then I recurse on both children with rem minus the node's value, and pop the value on the way out. Every append has a matching pop, which is what keeps path correct for the next branch. The trap is returning early after a match: the pop is skipped and a stale value stays in every later path. The walk is
O(N), but each saved path costs up to H to copy, so the time is O(N times H), with O(H) extra space for path and the recursion stack.
Complexity & Mathematical Proof
O(N · H)
Look at the execution steps: Backtracking DFS traverses every node once. At each leaf that sums to target, copies current path of length H into output list. Copying takes O(H) time.
O(H) path + recursion stack
Call stack and mutable path array both take O(H) auxiliary space.
T(N, H) = O(N) + K · O(H) = O(N · H)
Derivation Progression
O(N) node visits
Visits all N nodes and maintains path array with append/pop in O(1).
K valid paths × O(H) copy cost
When targetSum is met at leaf, snapshots path into results in O(H) time.
O(N + K · H) ≤ O(N · H)
Bounded by number of valid leaf paths times height.
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) Recursion stack frames
O(H) Mutable path array (output list excluded)
O(K · H) Result list of valid paths
Boundary Best / Worst Cases
if no valid paths.
.
if many valid paths on full tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "root-to-leaf paths where sum equals targetSum". Whole paths must be listed: Root-to-Leaf Paths, one shared path pushed on entry and popped on exit.
. Time budget for traversal + for copying valid paths to the result list.
A chain of 5000 nodes is past CPython's default recursion limit of 1000: raise the limit, or walk with an explicit stack of (node, rem, depth) and cut path back to depth before each append.
Path Sum II (LeetCode 113)
You're given the root of a binary tree and a target number targetSum. Collect every root-to-leaf path whose node values add up to targetSum, with each path reported as a plain list of values (not node objects).
A root-to-leaf path always starts at the root and ends at a leaf — a node with no children at all.
Worked Examples
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22[[5,4,11,2],[5,8,4,5]]root = [1,2,3], targetSum = 5[]3 and 4; neither is 5.root = [1,2], targetSum = 0[]1 -> 2, sums to 3, not 0.⚖️Formal Constraints & Bounds
The number of nodes in the tree is in the range
[0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Core Insight
Sharing a single path buffer and reverting it with path.pop() reduces memory from O(N^2) to O(H) auxiliary space.
Real-World Scenario & Production Applications
Rule-engine execution traces, financial ledger audit trail verification, and decision-tree classification paths.
Subproblems & Recurrence Decomposition3 Phases
Carry the accumulated sum and the current root-to-node path as recursion parameters; append the current node's value to the path before recursing into children.
path.append(node.val)
remaining = targetSum - node.valStep-by-Step Execution Trace Table
| Call Frame | Node Visited | Active Path Buffer path | Running Remaining Sum remain | Leaf Check (not left and not right) | Action / Backtrack Status |
|---|---|---|---|---|---|
| 1 | 5 (root) | [5] | False | Recurse left child 4 | |
| 2 | 4 | [5, 4] | False | Recurse left child 11 | |
| 3 | 11 | [5, 4, 11] | False | Recurse left child 7 | |
| 4 | 7 | [5, 4, 11, 7] | True (Leaf) | Remain $ | |
eq 0 ⟹$ no match. Backtrack: path.pop() -> 7 | |||||
| 5 | 2 | [5, 4, 11, 2] | True (Leaf) | Target matched! Snapshot results.append([5, 4, 11, 2]). Backtrack: path.pop() -> 2 | |
| - | - | [5, 4] | 13 | - | Backtrack from 11 (path.pop() -> 11), then backtrack from 4 (path.pop() -> 4) |
| 6 | 8 | [5, 8] | False | Recurse left child 13 | |
| 7 | 13 | [5, 8, 13] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 13 | |||||
| 8 | 4 | [5, 8, 4] | False | Recurse left child 5 | |
| 9 | 5 | [5, 8, 4, 5] | True (Leaf) | Target matched! Snapshot results.append([5, 8, 4, 5]). Backtrack: path.pop() -> 5 | |
| 10 | 1 | [5, 8, 4, 1] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 1 | |||||
| - | - | [] | 22 | - | Search completes; return [[5, 4, 11, 2], [5, 8, 4, 5]] |
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22[[5,4,11,2],[5,8,4,5]]| Call Frame | Node Visited | Active Path Buffer path | Running Remaining Sum remain | Leaf Check (not left and not right) | Action / Backtrack Status |
|---|---|---|---|---|---|
| 1 | 5 (root) | [5] | False | Recurse left child 4 | |
| 2 | 4 | [5, 4] | False | Recurse left child 11 | |
| 3 | 11 | [5, 4, 11] | False | Recurse left child 7 | |
| 4 | 7 | [5, 4, 11, 7] | True (Leaf) | Remain $ | |
eq 0 ⟹$ no match. Backtrack: path.pop() -> 7 | |||||
| 5 | 2 | [5, 4, 11, 2] | True (Leaf) | Target matched! Snapshot results.append([5, 4, 11, 2]). Backtrack: path.pop() -> 2 | |
| - | - | [5, 4] | 13 | - | Backtrack from 11 (path.pop() -> 11), then backtrack from 4 (path.pop() -> 4) |
| 6 | 8 | [5, 8] | False | Recurse left child 13 | |
| 7 | 13 | [5, 8, 13] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 13 | |||||
| 8 | 4 | [5, 8, 4] | False | Recurse left child 5 | |
| 9 | 5 | [5, 8, 4, 5] | True (Leaf) | Target matched! Snapshot results.append([5, 8, 4, 5]). Backtrack: path.pop() -> 5 | |
| 10 | 1 | [5, 8, 4, 1] | True (Leaf) | Remain $ | |
eq 0$. Backtrack: path.pop() -> 1 | |||||
| - | - | [] | 22 | - | Search completes; return [[5, 4, 11, 2], [5, 8, 4, 5]] |
| 1 | results: List[List[int]] = [] |
| 2 | path: List[int] = [] |
| 3 | def dfs(node, rem): |
| 4 | if not node: |
| 5 | return |
| 6 | path.append(node.val) |
| 7 | if not node.left and not node.right and rem == node.val: |
| 8 | results.append(list(path)) |
| 9 | dfs(node.left, rem - node.val) |
| 10 | dfs(node.right, rem - node.val) |
| 11 | path.pop() |
| 12 | dfs(root, targetSum) |
| 13 | return results |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every earlier DFS archetype in this pattern only returned a value upward. This one needs to return the actual route taken — and reusing one shared list for every branch requires cleaning up after yourself.
🧭 The Analogy: A Tour Guide's Reusable Clipboard
Imagine a tour guide leading groups down every possible branching trail from a starting point, using a single shared clipboard to jot down each stop as they walk. When the group reaches a destination that satisfies the goal (a leaf whose path sums to the target), the guide photographs the clipboard as it currently stands — a snapshot of this one specific route. But before backtracking to try a different branch, the guide erases the last entry they wrote. Why? Because the next branch they explore needs the clipboard to look exactly like it did before this branch was ever tried — otherwise leftover entries from an abandoned route would contaminate every future path.
🔑 The Key Idea in the Code
results.append(list(path)) (a copy) versus results.append(path) (a reference) is the detail that silently breaks this pattern the first time most people write it — without the copy, every recorded "answer" points at the same list object, which keeps changing, and they'd all end up empty by the time the recursion finishes.
Appending mutable path reference to results: Appending
pathinstead of a snapshot copypath[:]orlist(path)results in an output full of empty lists after backtracking pops.Evaluating target sum at non-leaf nodes: Triggering answer collection when
remaining == 0without verifyingnot node.left and not node.rightcounts internal prefix paths that don't terminate at a leaf.Backtrack popping in base case: If you pop inside an early return branch for
node is None, you double-pop parent nodes. Maintain symmetry: append on entry, pop on exit.Early exit with negative numbers: Pruning search when
remaining < 0fails when negative numbers exist later in the tree.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement asks for every root-to-leaf path whose values add up to targetSum, returned as the lists of values themselves: whole paths must be listed, not just counted, which is the Root-to-Leaf Paths signal.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
At each node: path.append(node.val); if the node is a leaf and rem == node.val, save list(path); recurse on both children with rem - node.val; then path.pop().
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: pop after both children, even when the node matched.
Values and
targetSumcan be negative, so never stop a branch early because its running sum has passed the target: on[-2,null,-3]withtargetSum = -5, the answer needs both nodes.A path holds at least one node: an empty tree returns
[]even whentargetSum = 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Root-to-Leaf Paths. I keep one shared list, path, that always holds exactly the nodes from the root to where I am, plus rem, what the path still needs, starting at targetSum. At each node I append its value. If it's a leaf and rem equals its value, the path works, so I save a copy of the list, because the shared list keeps changing after I return. Then I recurse on both children with rem minus the node's value, and pop the value on the way out. Every append has a matching pop, which is what keeps path correct for the next branch. The trap is returning early after a match: the pop is skipped and a stale value stays in every later path. The walk is
O(N), but each saved path costs up to H to copy, so the time is O(N times H), with O(H) extra space for path and the recursion stack.
Complexity & Mathematical Proof
O(N · H)
Look at the execution steps: Backtracking DFS traverses every node once. At each leaf that sums to target, copies current path of length H into output list. Copying takes O(H) time.
O(H) path + recursion stack
Call stack and mutable path array both take O(H) auxiliary space.
T(N, H) = O(N) + K · O(H) = O(N · H)
Derivation Progression
O(N) node visits
Visits all N nodes and maintains path array with append/pop in O(1).
K valid paths × O(H) copy cost
When targetSum is met at leaf, snapshots path into results in O(H) time.
O(N + K · H) ≤ O(N · H)
Bounded by number of valid leaf paths times height.
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) Recursion stack frames
O(H) Mutable path array (output list excluded)
O(K · H) Result list of valid paths
Boundary Best / Worst Cases
if no valid paths.
.
if many valid paths on full tree.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "root-to-leaf paths where sum equals targetSum". Whole paths must be listed: Root-to-Leaf Paths, one shared path pushed on entry and popped on exit.
. Time budget for traversal + for copying valid paths to the result list.
A chain of 5000 nodes is past CPython's default recursion limit of 1000: raise the limit, or walk with an explicit stack of (node, rem, depth) and cut path back to depth before each append.