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.
Using a recursive DFS, traverse each path from root to leaf, maintaining the current path and its corresponding sum. When a leaf is reached, check if the path's sum matches the targetSum. Use backtracking to explore all paths.
We use a helper function, dfs, to recursively explore paths. We store current paths and their sums in arrays to keep track of potential solutions. When a solution is found at a leaf node, it is added to the result set, and backtracking ensures all paths are checked.
Time Complexity: O(N), where N is the number of nodes in the tree.
Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.
An iterative approach using a stack can also be used for this problem. We maintain stacks that parallel traditional DFS traversal with added structures to track path and cumulative sum states for efficient exploration of all feasible root-to-leaf paths.
This C++ solution employs a stack to simulate DFS traversal iteratively. The stack holds node, cumulative sum, and path data. As each node is processed, we check for valid paths and update the result list accordingly. Paths are extended by exploring left and right children, augmented by the current node value.
C++
JavaScript
Time Complexity: O(N), as each node is processed exactly once.
Space Complexity: O(N), since results and stack can store all nodes during worst-case full-tree traversal.
We start from the root node, recursively traverse all paths from the root node to the leaf nodes, and record the path sum. When we traverse to a leaf node, if the current path sum equals targetSum, then we add this path to the answer.
The time complexity is O(n^2), where n is the number of nodes in the binary tree. The space complexity is O(n).
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search | Time Complexity: O(N), where N is the number of nodes in the tree. Space Complexity: O(H), where H is the height of the tree, due to the recursion stack. |
| Iterative Depth-First Search with Stack | Time Complexity: O(N), as each node is processed exactly once. Space Complexity: O(N), since results and stack can store all nodes during worst-case full-tree traversal. |
| DFS | — |
| 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. |
Path Sum II | Bloomberg | LinkedIn | Amazon | Bloomberg | Quora | Leetcode 113 • codestorywithMIK • 13,576 views views
Watch 9 more video solutions →Practice Path Sum II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor