Skip to main content

113 - Path Sum II

Difficulty: Medium | Pattern: Tree DFS + Backtracking | Company tags: Amazon, Microsoft, Bloomberg

Problem Statement​

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 the node values.

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]]

Algorithm Flow​

Approach: DFS + Backtracking — O(n²)​

Key insight: DFS from root to every leaf, maintaining a current path. When we reach a leaf and the remaining target is 0, copy the path to results. Use backtracking: add node before recursing, remove after.

def pathSum(root, targetSum: int) -> list[list[int]]:
    result = []
    
    def dfs(node, remaining, path):
        if not node:
            return
        path.append(node.val)
        remaining -= node.val
        
        # Leaf node and sum matches
        if not node.left and not node.right and remaining == 0:
            result.append(list(path))  # copy the path
        else:
            dfs(node.left, remaining, path)
            dfs(node.right, remaining, path)
        
        path.pop()  # backtrack
    
    dfs(root, targetSum, [])
    return result

Dry Run​

Tree: 5 → [4→[11→[7,2]], 8→[13, 4→[5,1]]], targetSum=22

dfs(5, 22, []):  path=[5], remaining=17
  dfs(4, 17, [5,4]):  remaining=13
    dfs(11, 13, [5,4,11]):  remaining=2
      dfs(7, 2, [5,4,11,7]): leaf, remaining=-5 ≠ 0
      dfs(2, 2, [5,4,11,2]): leaf, remaining=0 ✓ → append [5,4,11,2]
  dfs(8, 17, [5,8]):  remaining=9
    dfs(13, 9, [5,8,13]): leaf, remaining=-4 ≠ 0
    dfs(4, 9, [5,8,4]):  remaining=5
      dfs(5, 5, [5,8,4,5]): leaf, remaining=0 ✓ → append [5,8,4,5]
      dfs(1, 5, [5,8,4,1]): leaf, remaining=4 ≠ 0

Result: [[5,4,11,2],[5,8,4,5]] ✓

Why list(path) Not path​

result.append(path) would append a reference to the same mutable list, which gets modified by backtracking. Always copy: result.append(list(path)) or result.append(path[:]).

Comparison with LC 112​

ProblemReturns
112 - Path Sumbool (any valid path?)
113 - Path Sum IIlist of all valid paths

Same DFS structure — 113 just collects and copies each valid path.

Complexity​

  • Time: O(n²) — O(n) nodes visited, O(n) to copy each path in worst case
  • Space: O(n) — recursion stack + path array

Key Terms​

TermDefinition
BacktrackingUndoing a choice (path.pop()) after exploring it, so the same path list can be reused for sibling branches.
Path accumulationBuilding up a candidate path incrementally as DFS descends, rather than recomputing it from scratch at each node.
Shallow copy (list(path))Creating a new list with the same elements so future mutations to path don't affect the stored result.
Root-to-leaf pathA full path from the root to a leaf node; the unit of output for this problem.
DFS + BacktrackingThe combined pattern of depth-first traversal with explicit state mutation and restoration, common to path-enumeration problems.

FAQ​

  1. Can this be solved without extra space? No — you need O(n) for the output paths and O(h) for the recursion stack; this is inherent to enumerating all matching paths.
  2. What if the input graph (tree) had a cycle? Binary trees are acyclic by definition, so this doesn't apply here; if it did, DFS would need a visited set to avoid infinite recursion.
  3. Why must we copy path into the result instead of appending it directly? path is a single mutable list reused across the whole traversal; appending a reference would mean all stored "paths" end up reflecting the final state of path after backtracking pops everything.
  4. What's the difference between this and 112 - Path Sum? 112 only needs to know if any valid path exists (returns bool, can short-circuit); 113 must find and collect every valid path, so it can't stop early and must copy state at each match.
  5. How would this change if we needed the path with the maximum or minimum sum instead of an exact target? You'd drop the target-matching condition and instead track/compare sums as you go, updating a "best path" variable at each leaf instead of appending every match.

Quick Revision​

  • Problem: return all root-to-leaf paths whose values sum to targetSum.
  • Approach: DFS while maintaining a running path list and remaining sum.
  • Append node.val to path before recursing, pop it after (backtracking).
  • At a leaf with remaining == 0, copy path into the result list.
  • Must use list(path) or path[:] — never append the mutable path reference directly.
  • Recurse into both children when not at a matching leaf.
  • Time: O(n²) worst case due to path copies; Space: O(n) for recursion + path storage.
  • Same DFS skeleton as 112 - Path Sum, but collects all paths instead of returning a boolean.
  • 112 - Path Sum — same DFS pattern, but only checks if any valid path exists (returns boolean).
  • Pattern: DFS + Backtracking with path accumulation, also seen in "Sum Root to Leaf Numbers" and "Binary Tree Paths".