DSA problem
Path Sum II
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths whose node values sum to targetSum. Each path should be returned as a list of node values, in any order.
This is a classic preorder-DFS with backtracking. We descend from the root carrying two pieces of state: the current path (a mutable list of values from the root to the node we are visiting) and the remaining amount we still need to accumulate (remaining = targetSum - running_sum). At every step we push the current value onto the path; when we reach a leaf we check whether the remaining amount is exactly zero, and if so we snapshot the path (a copy!) into the result list.
The "snapshot" detail matters: because we share a single path list across the entire traversal — appending before recursing and popping afterwards — we must make a copy when adding it to the answer; otherwise the popped values would corrupt the saved result. This is the single most common bug in this problem.
Time complexity is O(n * h) in the worst case: each of the n nodes is visited once, but for every matching root-to-leaf path of length h we also pay O(h) to copy. Space complexity is O(h) for the recursion stack plus O(answer-size) for the output. The same problem appears in many disguises (e.g. "all ways to reach a target") so the pattern — share state, mutate, snapshot, backtrack — is worth internalizing.
Examples
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22[[5,4,11,2],[5,8,4,5]]root = [1,2,3], targetSum = 5[]root = [1,2], targetSum = 0[]Constraints
- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.