113. Path Sum II — DSA Atlas

113

MediumTrees and Binary Search TreesDFS with backtrackingBacktracking to collect qualifying paths

Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths whose node values sum to targetSum. Each path is returned as the list of node values from root to leaf, and the order of the paths does not matter.

Open official problem prompt ↗

In plain English

Produce the list of every complete root-to-leaf route whose values total targetSum.

Picture it like this

Explore a cave with a rope you pay out as you go and reel back at dead ends; every time you reach an exit at exactly the right depth, you photograph the current rope layout.

Example

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Why: Both 5+4+11+2 and 5+8+4+5 equal 22, and both end at leaves.

Constraints

The number of nodes is in the range [0, 5000]-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000

Pattern lesson

See the pattern, then code

Backtracking to collect qualifying paths

↗

Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Maintain one shared path list; push a node's value on entry and pop it on exit so the list always mirrors the current route, and snapshot it whenever a leaf hits the target.

New words, made simpleKnow these before the algorithm

Backtracking: Undoing the last choice (pop) after exploring it so the shared state is reusable
Snapshot: A copy of the current path list, since the list itself keeps mutating
Remaining: targetSum minus values already on the path

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Recurse returning new lists

Works but allocates many intermediate lists at every level.

Each call returns fresh path lists built by prepending the current value to child results.

Time O(n^2)Space O(n^2)

Best choiceOne shared path with push/pop

Minimal allocation; copies happen only for actual answers.

Mutate a single list, copy it only on a successful leaf, and pop on exit.

Time O(n^2)Space O(n)

The rule we keep true

Invariant

Whenever `dfs(node, remaining)` runs, `path` holds exactly the values from the root to that node's parent plus about-to-be-added node, and `remaining` is targetSum minus the ancestor values.

Why this is correct

Reasoning

The push before recursion and pop after guarantee `path` always equals the current route. A copy is taken only when a leaf's value matches the remaining target, so `res` collects precisely the qualifying root-to-leaf paths and nothing partial.

The algorithm in three movesSay these aloud before coding

1Append the current node value and decrement the remaining target

path=[5,4,11,2] -> save copy

2At a leaf, if the remaining equals the leaf value, snapshot a copy of the path

backtrack to [5]

3Otherwise recurse into both children

path=[5,8,4,5] -> save copy

4Pop the value before returning so siblings start clean

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

112

1 · Read5,4,11 then leaf 2

2 · AskIs 2 a leaf with remaining 2?

3 · Update statepath=[5,4,11,2]

4 · ResultYes — append copy [5,4,11,2] to res

Key takeaway

One of the two answer paths, [5,4,11,2], captured at the moment its leaf is reached.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-8Enter and record
Null guard first, then push the value so the path reflects this node.
2
Lines 9-10Leaf success
Only a leaf that exactly consumes the remaining target earns a snapshot copy.
3
Lines 14Backtrack
The pop runs on every path so siblings and ancestors never see stale values.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Empty tree returns an empty list
No qualifying path returns an empty list, not a list with an empty path
Multiple valid paths must all appear
Negative values mean the running sum can dip and recover, so you cannot prune on overshoot

Common beginner mistakes

Appending `path` itself instead of `path[:]` — all entries would then alias one list that later empties
Forgetting to pop, which corrupts sibling exploration
Checking the target at internal nodes rather than only at leaves

Check your understanding

Why must we append `path[:]` rather than `path`?

PyPython 3 · solution.py

Optimal

1class Solution:2    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:3        res: List[List[int]] = []4        path: List[int] = []5        def dfs(node: Optional[TreeNode], remaining: int) -> None:6            if not node:7                return8            path.append(node.val)9            if not node.left and not node.right and remaining == node.val:10                res.append(path[:])11            else:12                dfs(node.left, remaining - node.val)13                dfs(node.right, remaining - node.val)14            path.pop()15        dfs(root, targetSum)16        return res

Time complexityO(n^2)Optimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloomberg

Path Sum II

Path Sum II

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trees and Binary Search Trees