Path Sum II
Understanding the Problem
We need to find every path from the root down to a leaf node whose node values add up to a given target.
Paths must go from root to leaf. Stopping at an internal node doesn't count, even if the sum happens to match at that point. We return all valid paths, not just one. And the node values can be negative, which means a path's running sum can decrease as we go deeper. That rules out any early termination like "stop exploring once the sum already exceeds the target," since a negative value further down could bring it back to the target.
The work is to explore every root-to-leaf path while tracking which nodes are on the current path and what the running sum is.
Key Constraints:
Number of nodes up to 5000→ The tree is small enough that the path-copying cost in some approaches stays acceptable, but we still want to avoid redundant work where we can.-1000 <= Node.val <= 1000→ Node values can be negative, so we cannot prune a branch when its running sum passes the target. A negative descendant could bring the sum back down.-1000 <= targetSum <= 1000→ The target can be negative, and the running-sum logic handles that without any special case.
Approach 1: DFS with Path Copying
Intuition
Depth-first search fits this problem: it walks one root-to-leaf route at a time, and at each node we can carry the path taken from the root down to that node. When we reach a leaf, we check whether the path sums to the target.
The simplest version creates a new copy of the path at every recursive call. Each node gets its own independent list, so one branch can never corrupt another's path. It is easy to reason about, at the cost of copying the path at every node.
Algorithm
- Start at the root with the full
targetSumas the remaining amount. - At each node, create a new list that includes all previous nodes plus the current node.
- If the current node is a leaf and the remaining amount equals the node's value, add this path to the result.
- Otherwise, recurse into the left and right children with
remaining - node.valand the new path. - Since each call gets its own copy, there is nothing to undo when control returns to the parent.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). We visit every node once, but at each node we copy the current path. In a skewed tree, copying takes O(n) per node, giving O(n^2) total.
- Space Complexity: O(n^2). Each recursion level creates a new path copy. In a skewed tree, copies at each level have lengths 1, 2, ..., n, totaling O(n^2).
The copy at every node is the part worth removing. The next approach keeps a single shared path and undoes each step on the way back up.
Approach 2: DFS with Backtracking (Optimal)
Intuition
Instead of copying the path at every node, we maintain a single path list that we modify in place. Before exploring a node's children, we add the node to the path. After both children are done, we remove the node. This add-then-remove step is backtracking.
This stays correct because the add and remove are paired with entering and leaving each node, which follows the call stack's last-in-first-out order. When DFS enters a node it appends to the path; when DFS finishes that node and returns to its caller it removes the last element. At any moment, the path holds exactly the nodes from the root down to the current node. The only copy happens when we reach a matching leaf, which is far rarer than visiting a node.
Algorithm
- Maintain a single
pathlist and aresultlist. - At each node, add the node's value to
path. - If the node is a leaf and the remaining sum equals the node's value, copy
pathintoresult. - Otherwise, recurse into the left and right children, passing
remaining - node.val. - After the children return (or after recording a match), remove the last element from
path(backtrack).
Visualization and Code
Loading animation...
- Time Complexity: O(n^2) worst case, O(n log n) for balanced trees. We visit each node once. At each valid leaf, we copy the path. In a balanced tree, paths have length O(log n) with at most O(n) leaves, so copying costs O(n log n) total.
- Space Complexity: O(n). The recursion stack goes as deep as the tree height: O(n) worst case, O(log n) for balanced trees. The single path list uses at most O(n) space.
Backtracking gives the best space usage, but it still relies on recursion and the call stack. The next approach replaces the call stack with an explicit one.
Approach 3: Iterative DFS with Explicit Stack
Intuition
We can run the same DFS using an explicit stack instead of the call stack. Each stack entry holds the current node, the remaining sum, and the path up to that node. With no recursion, the depth is bounded by the explicit stack rather than the runtime's call-stack limit, which matters for a deeply skewed tree where recursion could overflow.
The cost is that each entry carries its own copy of the path, since there is no single shared list to add to and remove from. That brings back the same copying overhead as Approach 1, so this is not faster, just a recursion-free alternative.
Algorithm
- Initialize a stack with a tuple:
(root, targetSum, [root.val]). - While the stack is not empty, pop the top entry.
- If the node is a leaf and the remaining sum equals the node's value, add the path to the result.
- If the node has a right child, push
(right, remaining - node.val, path + [right.val])onto the stack. - If the node has a left child, push
(left, remaining - node.val, path + [left.val])onto the stack. - Continue until the stack is empty.
Visualization and Code
Loading animation...
- Time Complexity: O(n^2). Same as Approach 1. We visit every node once, but each stack entry contains a path copy. In a skewed tree, copying costs O(n) per node.
- Space Complexity: O(n^2). Each stack entry stores a full path copy. In a skewed tree, the stack can hold up to n entries, each with a path of up to length n.