Path Sum II

You are given the root of a binary tree and an integer targetSum. A root-to-leaf path starts at the root and follows child links down to a leaf (a node with no children). Find every such path whose node values add up to exactly targetSum.

Return the paths as lists of node values, each listed from the root down to the leaf. The paths may be returned in any order, but the values inside each path must be in root-to-leaf order. Node values can be negative, and an empty tree has no paths.

The tree is given in level order, with null marking a missing child: [1, 2, 3, null, 4] is root 1 with children 2 and 3, and 4 is the right child of 2.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Trees: DFS · problem 89 of 169

Start simple

Collect every root-to-leaf path as a fresh list, then filter those whose sum equals the target: O(n·h) time and memory for tree height h, with extra copying.

The key idea

Every root-to-leaf path is visited exactly once by a depth-first search, so the only question is how to carry the path along cheaply.

Keep a single list path and a running remaining value. When the DFS enters a node, append its value and subtract it from remaining. If the node is a leaf and remaining is 0, the path is a match: append a copy of path to the answer (the list itself will keep changing). Otherwise recurse into the children. On the way back out, pop the node's value. This undo step is backtracking: it restores the list to exactly what the parent had, so siblings can reuse it.

Do not prune when the running sum overshoots or hits the target early: values can be negative, so a path that looks finished or too large can still end exactly on target at a leaf.

The DFS itself is O(n), and copying a matching path costs up to O(h), so the total is O(n·h) in the worst case.

Complexity

• Time: O(n·h)
• Space: O(h) besides the output

Python

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        paths, path = [], []

        def dfs(node, remaining):
            if not node:
                return
            path.append(node.val)
            remaining -= node.val
            if not node.left and not node.right:
                if remaining == 0:
                    paths.append(path[:])  # save a copy; path keeps changing
            else:
                dfs(node.left, remaining)
                dfs(node.right, remaining)
            path.pop()  # backtrack before returning to the parent

        dfs(root, targetSum)
        return paths

JavaScript

var pathSum = function(root, targetSum) {
  const paths = [], path = [];

  const dfs = (node, remaining) => {
    if (!node) return;
    path.push(node.val);
    remaining -= node.val;
    if (!node.left && !node.right) {
      if (remaining === 0) paths.push([...path]); // save a copy; path keeps changing
    } else {
      dfs(node.left, remaining);
      dfs(node.right, remaining);
    }
    path.pop(); // backtrack before returning to the parent
  };

  dfs(root, targetSum);
  return paths;
};

What the interviewer is checking

This checks recursive tree traversal with backtracking state: adding and removing from a shared path, copying on success, and handling the leaf-only and negative-value subtleties.

Mistakes to avoid

• Appending the shared path list itself instead of a copy, so every saved path ends up empty or identical.
• Accepting a path that reaches the target at an inner node instead of a leaf.
• Pruning when the sum exceeds the target, which is wrong with negative values.
• Forgetting to pop after visiting a node, which leaks values into sibling paths.

Follow-ups to expect

• Paths may start and end anywhere going down. (Prefix sums with a hash map.)
• Only count the matching paths. (Return counts, skip copying.)
• Avoid recursion for very deep trees. (Explicit stack with path state.)

In real software

Finding every chain in a hierarchy that meets a budget, such as category trees whose costs add up to a limit or call stacks whose total latency matches a threshold, uses the same DFS with backtracking.

Practice next