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.
1#include <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode() : val(0), left(nullptr), right(nullptr) {}
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15 void dfs(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& result) {
16 if (!root) return;
17 path.push_back(root->val);
18 targetSum -= root->val;
19 if (!root->left && !root->right && targetSum == 0) {
20 result.push_back(path);
21 } else {
22 dfs(root->left, targetSum, path, result);
23 dfs(root->right, targetSum, path, result);
24 }
25 path.pop_back();
26 }
27 vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
28 vector<vector<int>> result;
29 vector<int> path;
30 dfs(root, targetSum, path, result);
31 return result;
32 }
33};We define a recursive DFS function that traverses each path, checks for a matching sum at leaf nodes, and uses backtracking to remove nodes from the current path before returning to the previous call. This ensures all possible paths are explored.
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.
1#include <vector>
2#include <stack>
3using namespace std;
4
5struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
if (!root) return result;
stack<pair<TreeNode*, pair<int, vector<int>>>> stk;
stk.push({root, {root->val, {root->val}}});
while (!stk.empty()) {
auto [node, state] = stk.top(); stk.pop();
auto [currentSum, path] = state;
if (!node->left && !node->right && currentSum == targetSum) {
result.push_back(path);
}
if (node->right) {
path.push_back(node->right->val);
stk.push({node->right, {currentSum + node->right->val, path}});
path.pop_back();
}
if (node->left) {
path.push_back(node->left->val);
stk.push({node->left, {currentSum + node->left->val, path}});
path.pop_back();
}
}
return result;
}
};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 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.