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 <= 1000Path Sum II asks you to return all root-to-leaf paths in a binary tree where the sum of node values equals a given target. A natural strategy is to use Depth-First Search (DFS) combined with backtracking. As you traverse the tree, maintain a running path and the remaining sum needed to reach the target.
At each node, add the node value to the current path and subtract it from the remaining target. If you reach a leaf node and the remaining sum becomes zero, you have found a valid path and can store a copy of it. After exploring a branch, remove the current node from the path (backtrack) so the path can be reused for other branches.
This recursive DFS ensures every root-to-leaf path is explored. The approach efficiently tracks partial paths using a dynamic list or array. The time complexity is proportional to the number of nodes explored and possible paths, while the space complexity depends on recursion depth and stored paths.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Backtracking | O(N * H) in the worst case due to path copying | O(H) recursion stack, plus output storage |
NeetCode
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.
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.
1from typing import List, Optional
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5
In this Python solution, we perform a DFS and track the path and its cumulative sum. Upon meeting both the leaf and sum conditions, we add the path to the result using list operations for copying and backtracking.
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.
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.
1function TreeNode(val, left, right) {
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Path Sum II or similar tree path problems frequently appear in FAANG-style interviews. They test understanding of DFS traversal, recursion, and backtracking with trees.
A dynamic list or array is typically used to track the current path during DFS traversal. The binary tree structure itself guides the recursion, while the list helps record node values along each explored path.
The optimal approach uses Depth-First Search with backtracking. As you traverse from root to leaf, maintain the current path and remaining target sum. When a leaf node matches the target, store the path and backtrack to explore other possibilities.
Path Sum checks whether at least one root-to-leaf path equals the target sum. Path Sum II extends the problem by requiring you to return all such valid paths, which introduces the need to track and store paths during traversal.
This JavaScript solution leverages a stack for iterative DFS traversal. Each stack element tracks the node, cumulative sum, and path. When paths qualify as solutions at leaf nodes, they're aggregated into results using path concatenation for subsequent level exploration.