Watch 10 video solutions for Path Sum II, a medium level problem involving Backtracking, Tree, Depth-First Search. This walkthrough by NeetCode has 460,623 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: You are given the root of a binary tree and a target sum. The goal is to return every root-to-leaf path where the sum of node values equals the target. Each valid path must start at the root and end at a leaf node.
Approach 1: Recursive Depth-First Search with Backtracking (O(n) time, O(h) space)
This approach performs a depth-first traversal of the tree while keeping track of the current path and the remaining sum. At each node, append its value to the current path and subtract it from the remaining target. When you reach a leaf node, check whether the remaining sum equals the node value. If it does, copy the current path into the result list.
Backtracking is the key detail. After exploring a node’s children, remove the last element from the path before returning to the caller. This ensures the path reflects the correct state for the next branch. The traversal visits each node once, giving O(n) time complexity. The recursion stack and path storage use O(h) space, where h is the tree height. This technique combines depth-first search with backtracking on a binary tree.
Approach 2: Iterative Depth-First Search with Stack (O(n) time, O(h) space)
The same traversal can be implemented iteratively using an explicit stack. Each stack entry stores the current node, the remaining sum, and the path built so far. Start by pushing the root node with the initial target and an empty path. While the stack is not empty, pop the top state, update the path with the current node value, and check whether it forms a valid root-to-leaf path.
If the node has children, push them onto the stack along with the updated remaining sum and path copy. This simulates the recursive DFS call stack. The algorithm still processes each node once, resulting in O(n) time complexity, while the stack stores at most one path per level, using O(h) space in balanced trees.
Recommended for interviews: Recursive DFS with backtracking is the solution most interviewers expect. It clearly shows your understanding of tree traversal, path tracking, and state rollback. The iterative stack version demonstrates deeper control over recursion mechanics, but the recursive version is usually cleaner and faster to implement during interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Backtracking | O(n) | O(h) | Best general solution for tree path problems and the most common interview approach |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion or when explicit control over the traversal stack is preferred |