Path Sum II: Collecting All Valid Root-to-Leaf Paths

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values equals targetSum. Each path should be returned as a list of node values, not node references.

This is LeetCode 113: Path Sum II, and it builds directly on top of Path Sum. Where Path Sum asks "does a valid path exist?", Path Sum II asks "give me all of them." That one word, all, changes the solution from a simple boolean recursion to a DFS with path tracking and backtracking.

Why this problem matters

If you solved Path Sum, you already know how to carry a shrinking remainder from root to leaf. You subtract each node's value as you descend, and at a leaf, you check if the remainder is zero. That core idea does not change here.

What changes is the bookkeeping. Instead of returning True the moment you find one valid path, you need to:

1. Track the current path as you descend (append each node).
2. Collect a copy of the path when you find a match at a leaf.
3. Backtrack by removing the node after you finish exploring its subtrees.

This append-explore-pop pattern is the same backtracking skeleton you see in Subsets, Permutations, and Combination Sum. The difference is that here the recursion tree is a literal tree, not an abstract decision tree. That makes Path Sum II a great place to learn backtracking in a setting where the structure is easy to visualize.

The key insight

Maintain a single mutable list called path that represents the nodes from root to the current position. At every node:

1. Append the node's value to path.
2. Check if this node is a leaf and the remaining target (after subtracting this node's value) is zero. If so, save a copy of path to your results.
3. Recurse into both children.
4. Pop the last element from path to undo the choice before returning.

The pop is the backtracking step. It restores the path to its state before you entered this node, so when the parent explores the other child, the path is clean.

For the tree above with target 22:

• Path down the left side: [5, 4, 11, 7]. At leaf 7, remaining = 22 - 5 - 4 - 11 - 7 = -5. Not zero. Pop 7.
• Try right child: [5, 4, 11, 2]. At leaf 2, remaining = 22 - 5 - 4 - 11 - 2 = 0. Match! Save a copy.
• Backtrack all the way up, then explore the right subtree.
• Path [5, 8, 4, 5]. At leaf 5, remaining = 22 - 5 - 8 - 4 - 5 = 0. Match! Save a copy.

Final result: [[5, 4, 11, 2], [5, 8, 4, 5]].

The DFS solution

def path_sum(root, target_sum):
    result = []

    def dfs(node, remaining, path):
        if node is None:
            return
        path.append(node.val)
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            result.append(path[:])
        dfs(node.left, remaining, path)
        dfs(node.right, remaining, path)
        path.pop()

    dfs(root, target_sum, [])
    return result

Let's break this down line by line:

• result = [] holds all valid paths found during the traversal.
• path.append(node.val) adds the current node to the running path. This is the "choose" step.
• remaining -= node.val subtracts the current node's value from the running remainder, exactly like in Path Sum.
• The if block checks two things: is this node a leaf (both children are None), and is the remaining sum exactly zero? If both are true, path[:] makes a shallow copy and appends it to result. You must copy because path is mutable and will keep changing.
• The two recursive calls explore both children. Even after finding a match at a leaf, you still make both calls. They will hit the if node is None: return base case immediately since leaves have no children.
• path.pop() removes the current node from the path. This is the "unchoose" step, the backtracking that restores the path for the parent node's other branch.

Visual walkthrough

Let's trace the full DFS through the tree with target sum 22. Watch how the path list grows as you descend, and shrinks (via pop) as you backtrack.

The critical moments are Step 5 and Step 9. In Step 5, the path [5, 4, 11, 2] reaches a leaf where the remainder hits zero. A copy is saved. Then node 2 is popped, then 11, then 4, restoring the path to [5] so the right subtree can be explored fresh. In Step 9, the same thing happens with path [5, 8, 4, 5].

Complexity analysis

Time is O(n * h) in the worst case. You visit every node (O(n)), and each time you find a valid path you copy it, which takes O(h) where h is the height of the tree. In the worst case every root-to-leaf path is valid, so you make O(n / 2) copies of length O(h). The copying cost dominates when many paths match.

Space is O(h) for the recursion stack and the mutable path list, where h is the height of the tree. For a balanced tree, h = log n. For a skewed tree, h = n. This does not count the output list result, which in the worst case holds O(n) paths of length O(h).

Edge cases to watch for

• No valid paths: the tree exists but no root-to-leaf path sums to the target. The function returns an empty list [].
• Single node equals target: the root is a leaf with value equal to targetSum. Return [[root.val]].
• Single node does not equal target: root is a leaf but its value differs from the target. Return [].
• Multiple paths: the example above has two valid paths. The algorithm naturally collects all of them because it does not short-circuit.
• Negative node values: subtraction handles negatives naturally. A negative value increases the remainder, which might lead to a match later.
• All paths valid: every root-to-leaf path sums to the target. The function copies each one. The output size drives the total cost.

The building blocks

This problem combines two fundamental building blocks:

DFS path collection. You maintain a mutable list that represents the current root-to-node path. At each node, append the value. At leaves that satisfy a condition, copy the list into your results. After recursing, pop the value. The skeleton looks like this:

def dfs(node, path):
    if node is None:
        return
    path.append(node.val)
    if IS_LEAF(node) and CONDITION(path):
        result.append(path[:])
    dfs(node.left, path)
    dfs(node.right, path)
    path.pop()

This same skeleton appears in Binary Tree Paths (LeetCode 257), where you collect all root-to-leaf paths as strings, and in Sum Root to Leaf Numbers (LeetCode 129), where you accumulate a digit-based number along each path.

Backtracking with a running remainder. Instead of summing the entire path at each leaf to check the condition, you carry a running remainder that shrinks as you descend. At a leaf, you check if the remainder is zero. This avoids recomputing the sum from scratch at every leaf and keeps the per-node work at O(1).

Together, these two blocks turn Path Sum II into a clean ten-line solution. If you can write the DFS path collection skeleton from memory and know to subtract instead of sum, you can solve this problem without hesitation.

From understanding to recall

You just traced through a DFS that collects every root-to-leaf path summing to 22. You saw how appending, copying, and popping work together to explore all branches without corrupting the shared path list. The backtracking pattern is clear right now.

But will you remember to copy the path with path[:] instead of appending the reference? Will you remember that the pop goes after both recursive calls, not just after one? These details matter under interview pressure, and they are exactly the kind of thing that fades between practice sessions.

Spaced repetition locks in these details. You type the solution from scratch, first after a day, then three days, then a week. Each repetition forces you to reconstruct the append-check-recurse-pop sequence from memory. After a few rounds, the DFS path collection skeleton becomes automatic.

DFS path collection and backtracking with a running remainder are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually is far more effective than solving random problems and hoping the patterns stick.

Related posts

• Path Sum - The boolean version of this problem. Same tree, same remainder technique, but you return True/False instead of collecting paths. Start here if you have not solved it yet.
• Maximum Depth of Binary Tree - The foundational tree recursion problem. If Path Sum II is about passing state down, Maximum Depth is about collecting results going back up.