Path Sum II — Solution

Problem

Given a binary tree and a target sum, find every root-to-leaf path whose node values add up to exactly that target. A leaf is a node with no children — paths must terminate at a leaf.

[5,4,8,11,null,13,4,7,2,null,null,5,1]

• Input: root = above tree, targetSum = 22
• Output: [[5,4,11,2],[5,8,4,5]]
• Explanation: both paths reach a leaf and their values sum to 22

A counter-example: the path 5→8→4→1 sums to 18, not 22, so it is excluded even though it ends at a leaf.

Intuition

The problem is a classic tree enumeration: visit every root-to-leaf path and collect the ones that hit the target. The key insight is that you can track a decreasing remainder as you go deeper — subtract each node's value from the remaining target, and whenever you land on a leaf with zero left over, you have a valid path. Backtracking lets you undo each step and explore sibling subtrees without allocating a new list per call.

Solution — DFS with Backtracking

Carry a single mutable path list down the tree, appending each node's value and removing it after both children have been explored. When a leaf is reached with zero remaining sum, snapshot the current path into results.

1. Define a recursive helper that takes the current node, remaining target, and path list.
2. Return immediately if the node is null.
3. Append the node's value to the path and subtract it from the remaining target.
4. If the node is a leaf and remaining is exactly zero, copy the path into results.
5. Recurse into the left child, then the right child.
6. Pop the node's value from the path to backtrack before returning to the caller.

1def pathSum(root, targetSum):
2    result = []
3
4    def dfs(node, remaining, current_path):
5        if not node:
6            return
7
8        current_path.append(node.val)
9        remaining -= node.val
10
11        # Only record at a true leaf — nodes with one child don't count
12        if not node.left and not node.right and remaining == 0:
13            result.append(list(current_path))  # copy, not reference
14
15        dfs(node.left, remaining, current_path)
16        dfs(node.right, remaining, current_path)
17
18        current_path.pop()  # undo this node before returning to parent
19
20    dfs(root, targetSum, [])
21    return result

Time: O(n²) — every node is visited once, and copying a valid path takes O(h); in the worst case (many valid paths in a dense tree) total copy work reaches O(n²).

Space: O(h) auxiliary — the recursion stack and current path together hold at most one full root-to-leaf path at a time; output space for the collected paths is additional.

Complexity Summary

Common Mistakes

• Saving the path list directly instead of copying it — result.append(current_path) stores a reference to the same list that gets cleared during backtracking; result.append(list(current_path)) (or new ArrayList<>(currentPath) in Java) creates a snapshot.
• Triggering the result check at non-leaf nodes — a node with one child where remaining == 0 is NOT a valid endpoint; the condition must check not node.left and not node.right before recording the path.
• Forgetting to pop after recursing into both children — without the backtrack step, every subsequent path inherits garbage values from earlier branches, producing wrong-length paths.
• Skipping the single-node edge case — a tree with just one node whose value equals targetSum is a valid path; the leaf check naturally covers this, but forgetting the not node.left and not node.right guard does not.
• Confusing Path Sum with Path Sum III — this problem only allows root-to-leaf paths; Path Sum III allows paths starting and ending at any node, which requires a completely different prefix-sum approach.

Related Problems

• Path Sum — same DFS pattern but returns a boolean instead of collecting paths
• Path Sum III — extends to any node-to-node paths using prefix sums; same tree traversal but fundamentally different tracking
• Sum Root to Leaf Numbers — root-to-leaf paths treated as decimal numbers; same backtracking skeleton
• Binary Tree Maximum Path Sum — generalizes path sum to any node-to-node path and seeks the maximum, requiring a different return value from the recursive helper
• Path with Maximum Gold — grid-based backtracking collecting path values, same "accumulate then undo" structure