Path Sum II

A matching sum is only half the answer. The path must also end at a leaf.

That is the central trap in Path Sum II. An internal node may bring the running sum to targetSum, but its path is still incomplete if the node has a child. The reliable solution carries one root-to-current path, updates the remaining sum as it descends, records a copied path only at a qualifying leaf, and restores the path before exploring another branch.

The contract: matching root-to-leaf paths

Given a binary tree and an integer targetSum, return every path that:

1. Starts at the root.
2. Follows child links downward.
3. Ends at a leaf.
4. Has node values that sum to targetSum.

A leaf has no left child and no right child. The output contains node values, not node objects. An empty tree or a tree with no qualifying path produces an empty list.

For example:

        5
       / \
      4   8
     /   / \
   11   13  4
   / \      / \
  7   2    5   1

For targetSum = 22, the result is:

[
    [5, 4, 11, 2],
    [5, 8, 4, 5]
]

Both paths have the required sum, and both end at leaves.

Now consider:

    5
   /
  3
 /
1

For targetSum = 8, the prefix [5, 3] sums to 8, but it must not be returned. Node 3 is internal. The only root-to-leaf path is [5, 3, 1], whose sum is 9.

The endpoint condition controls the entire algorithm.

Recognize DFS with backtracking

The problem gives several strong signals:

• The input is a tree.
• Each answer is a complete route from root to leaf.
• The values along the route determine whether it qualifies.
• Every qualifying route must be found.

Depth-first search fits because one recursive call can represent one root-to-current route. A shared path list records that route:

1. Enter a node.
2. Append its value.
3. Explore its children.
4. Remove its value before returning.

That final removal is backtracking. It restores the list to the state it had before entering the node, allowing the same list to represent a sibling route.

Think of path as a trail of chalk. Add a mark when you walk into a node. Take a snapshot if the trail is a valid answer. Erase the mark when you walk back. The working trail is temporary state; the snapshots are the output.

This is different from a boolean path-sum problem, where finding one valid path may be enough. Here the search must continue after every match because the result can contain multiple paths.

Derive the state transition

A brute-force solution could enumerate every root-to-leaf path and calculate its sum afterward. That separates two operations that naturally belong together. While descending, we already know both the current path and its partial sum.

Instead, maintain:

dfs(node, remaining, path)

At each node:

1. Stop if the node is empty.
2. Append node.val to path.
3. Subtract node.val from remaining.
4. If the node is a leaf, record the path only when remaining == 0.
5. Otherwise, search both children.
6. Remove the node value before returning.

The key invariant is:

After the current node has been added, path contains exactly the root-to-current route, and remaining equals targetSum - sum(path).

When the algorithm executes:

remaining -= node.val

it updates the sum state by exactly the same value it added to the path state. The two variables stay synchronized.

At a leaf:

remaining == 0

means:

sum(path) == targetSum

But that condition is sufficient only because the algorithm checks it together with the leaf condition:

node.left is None and node.right is None

Both tests are required.

Why negative values prevent sign-based pruning

The tree may contain negative values. Therefore, these shortcuts are unsafe:

if remaining < 0:
    return

A later negative node can increase the remaining target again. A remaining value greater than zero also does not prove failure.

For example, if the current remaining target is -5, a later node with value -7 changes it to 2. The path may still eventually reach zero.

The safe rule is simple: do not prune based only on the sign of remaining. Continue until the search reaches a leaf or an empty subtree.

Why accepted paths must be copied

path is mutable shared state. When a valid path is found, store a snapshot:

result.append(path.copy())

Do not store the list itself:

result.append(path)  # Wrong

If the same list object is placed in the result, later append() and pop() operations continue changing it. You intended to preserve the path at one moment; you stored a live reference to traversal state.

This bug often survives a quick visual inspection because the traversal itself looks correct. The failure appears only when you inspect the final result.

Correctness: why the algorithm returns exactly the answers

The solution depends on four claims.

The path and remaining target stay synchronized

When a node is added, its value is appended to path and subtracted from remaining. Therefore:

remaining = targetSum - sum(path)

continues to hold throughout the traversal.

Every root-to-leaf path is explored

At every non-leaf node, the algorithm explores each existing child. Repeating this process reaches every leaf reachable from the root. When a leaf is visited, path is exactly one root-to-leaf path.

No candidate route is skipped.

Every recorded path is valid

The algorithm records a path only when:

node is a leaf
and
remaining == 0

The invariant proves that remaining == 0 means the path values sum to targetSum. The leaf check proves that the path has the required endpoint. Therefore, every recorded path is valid.

No branch contaminates another

After exploring a node and its descendants, the algorithm removes the value added for that node. Before another branch begins, path again contains only the nodes shared by both branches.

The result remains stable because accepted paths were copied before backtracking changed the working list.

Dry run the state

Using the first tree with target 22, the left branch behaves like this:

Node	Path after append	Remaining	Action
5	[5]	17	Descend
4	[5, 4]	13	Descend
11	[5, 4, 11]	2	Descend
7	[5, 4, 11, 7]	-5	Failed leaf; remove 7
2	[5, 4, 11, 2]	0	Copy the path; remove 2
return from 11	[5, 4, 11]	—	Remove 11
return from 4	[5, 4]	—	Remove 4

The negative remaining value at node 7 is not a pruning signal. The algorithm simply reaches a leaf, sees that the sum is wrong, and backtracks.

The right-side match follows the same state transition:

[5]          remaining 17
[5, 8]       remaining 9
[5, 8, 4]    remaining 5
[5, 8, 4, 5] remaining 0  -> copy the path

After recording the path, the traversal still removes 5, then 4, then 8. The stored result does not change because it is a separate list.

The smaller counterexample exposes the leaf condition:

    5
   /
  3
 /
1

At node 3:

path = [5, 3]
remaining = 0

The sum matches, but 3 has a child. The algorithm must continue to node 1, where the remaining value becomes -1. The prefix [5, 3] is never recorded.

Python implementation

The recursive version is the clearest way to derive the invariant. However, a highly skewed tree can have depth close to the number of nodes, and that can exceed Python's practical recursion depth. For a submission that should handle the full stated tree shape, use an explicit stack.

The stack below simulates recursive entry and return:

• An enter frame adds a node to path.
• An exit frame removes that node.
• Children are pushed in reverse order so the left child is processed first.

from typing import List, Optional


class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right


def path_sum(root: Optional[TreeNode], target_sum: int) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    if root is None:
        return result

    # Each frame is (node, remaining_before_node, is_exit_frame).
    stack = [(root, target_sum, False)]

    while stack:
        node, remaining, is_exit_frame = stack.pop()

        if is_exit_frame:
            path.pop()
            continue

        path.append(node.val)
        remaining -= node.val

        is_leaf = node.left is None and node.right is None

        if is_leaf:
            if remaining == 0:
                result.append(path.copy())

            # No exit frame was created for a leaf.
            path.pop()
            continue

        # Remove this node after both children have been processed.
        stack.append((node, remaining, True))

        # Push right first so left is processed first.
        if node.right is not None:
            stack.append((node.right, remaining, False))

        if node.left is not None:
            stack.append((node.left, remaining, False))

    return result

Each piece of state has a specific obligation:

• result stores completed answer paths.
• path stores the current root-to-node route.
• remaining stores the target still required after the route before the current node.
• An exit frame marks the point where the current node must be removed.
• path.copy() freezes a valid result before traversal state changes.

The ordering matters. When an internal node is entered, its exit frame is pushed before its children. The stack then processes the children and reaches the exit frame only after both branches finish. That is the iterative equivalent of recursive backtracking.

The empty-tree check handles root is None. A missing child is simply not pushed. A leaf is popped immediately because it has no child frames and therefore needs no delayed exit frame.

Complexity and edge cases

Let:

• n be the number of nodes.
• h be the tree height.
• L be the total number of values across all returned paths.

Every node is entered once and exited once, so traversal costs O(n). Copying each accepted path costs its length. The output-aware total is therefore:

O(n + L)

The auxiliary space is O(h) for the explicit DFS stack and the current path. The returned output requires a separate O(L) space.

Important edge cases:

• Empty tree: returns [].
• Single matching node: the root is also a leaf, so [root.val] is returned.
• Single nonmatching node: returns [].
• Target sum zero: a path qualifies only if its complete root-to-leaf sum is zero.
• Negative values: never prune based only on whether remaining is positive or negative.
• Duplicate values: repeated values are valid; paths are returned by value.
• Internal prefix match: reaching zero before a leaf does not produce an answer.
• Multiple matches: continue searching after recording one path.
• Skewed tree: the explicit stack avoids Python recursion-depth limitations.

The interview-ready reasoning

When explaining this Path Sum II solution, keep the chain visible:

1. The answer must be a root-to-leaf path, not merely a matching prefix.
2. DFS explores every possible route.
3. path records the current route.
4. remaining stays synchronized with the values in path.
5. Record only when the current node is a leaf and remaining == 0.
6. Copy accepted paths because the working list is mutable.
7. Undo the current node before exploring another branch.
8. Do not prune based only on the sign of the remaining sum.

The transferable pattern is broader than this one tree problem: when a search asks for every complete route and the answer depends on the route's accumulated state, carry that state forward, commit only at the required terminal condition, and undo shared state when leaving the branch.

Carry the route. Check the endpoint. Snapshot the answer. Restore the state.