Watch 10 video solutions for Path Sum II, a medium level problem involving Backtracking, Tree, Depth-First Search. This walkthrough by codestorywithMIK has 13,576 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
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]] Explanation: There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22
Example 2:
Input: root = [1,2,3], targetSum = 5 Output: []
Example 3:
Input: root = [1,2], targetSum = 0 Output: []
Constraints:
[0, 5000].-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000Problem Overview: Given a binary tree and a target sum, return all root-to-leaf paths where the sum of node values equals the target. A path must start at the root and end at a leaf node, and you need to return every valid path.
Approach 1: Recursive Depth-First Search with Backtracking (O(n) time, O(h) space)
This approach performs a depth-first traversal from the root while maintaining the current path and remaining sum. At each node, append the node value to the path and subtract it from the remaining target. When a leaf node is reached and the remaining sum becomes zero, copy the current path into the result list. Backtracking is critical: after exploring a node’s children, remove the node from the path so the same list can be reused for other branches. Each node is visited once, giving O(n) traversal time where n is the number of nodes, while the recursion stack uses O(h) space where h is the tree height. This technique combines depth-first search with backtracking to efficiently explore every root-to-leaf path.
Approach 2: Iterative DFS with Stack (O(n) time, O(h) space)
An iterative variant replaces recursion with an explicit stack. Each stack entry stores the current node, the remaining sum, and the path taken so far. Start by pushing the root node and its value. Pop nodes from the stack, update the path and remaining sum, and push child nodes with updated state. When a leaf node is encountered and the remaining sum equals the node value, add the path to the result list. The traversal order still mimics DFS but avoids recursion, which can be helpful in environments with limited recursion depth. The algorithm still visits every node once, resulting in O(n) time complexity and O(h) auxiliary space for the stack in a balanced binary tree.
Recommended for interviews: Recursive DFS with backtracking is the expected solution. Interviewers want to see that you can track a path, update a running sum, and undo state changes when returning from recursion. The iterative stack version demonstrates deeper understanding of DFS mechanics, but the recursive version is usually faster to implement and easier to reason about during an interview.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Backtracking | O(n) | O(h) | Best general solution for exploring all root-to-leaf paths in a binary tree. |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion or when stack-based traversal is preferred. |