Path Sum II
Path Sum II is a medium trees & bst problem solved with the backtracking pattern.
The best approach, optimal (dfs backtracking with remaining sum), runs in O(n + total length of the answer paths) time and O(h) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (collect every path, then filter) up.
Problem
Given the root of a binary tree and an integer targetSum, return every root-to-leaf path whose node values add up to targetSum. Each path is a list of the node values from the root down to the leaf.
A leaf is a node with no children. The paths may be returned in any order.
Examples
Example 1
- Input
root = [6, 2, 3, 4, 4, 1, 3], targetSum = 12- Output
[[6, 2, 4], [6, 2, 4], [6, 3, 3]]- Why
- 6 + 2 + 4 = 12 twice (two different leaves with value 4) and 6 + 3 + 3 = 12; 6 + 3 + 1 = 10 does not count.
Example 2
- Input
root = [1, -2, 3, null, 5], targetSum = 4- Output
[[1, -2, 5], [1, 3]]- Why
- Negative values are allowed; paths can have different lengths.
Example 3
- Input
root = [], targetSum = 0- Output
[]- Why
- An empty tree has no root-to-leaf paths, even for a target of 0.
Constraints
- The number of nodes is in the range
[0, 5000]. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (collect every path, then filter) | O(n · h) | O(n · h) |
| Optimal (DFS backtracking with remaining sum) | O(n + total length of the answer paths) | O(h) |
1Brute force (collect every path, then filter)
O(n · h)Each of the n nodes copies a path of length up to h (the height); summing the stored paths costs the same.O(n · h)Every leaf's full path is stored, and every call holds its own copy.Generate every root-to-leaf path as its own fresh list (copying the path at each step), then keep the ones whose values add up to the target. Simple, but it copies the path at every node.
- DFS from the root with a list
path; at each node make a new listpath + [node.val]. - At a leaf, store that list in
allPaths. - After the DFS, return the lists in
allPathswhose sum equalstargetSum.
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> allPaths = new ArrayList<>();
collect(root, new ArrayList<>(), allPaths);
List<List<Integer>> res = new ArrayList<>();
for (List<Integer> p : allPaths) {
int sum = 0;
for (int v : p) sum += v;
if (sum == targetSum) res.add(p);
}
return res;
}
private void collect(TreeNode node, List<Integer> path, List<List<Integer>> allPaths) {
if (node == null) return;
List<Integer> next = new ArrayList<>(path);
next.add(node.val);
if (node.left == null && node.right == null) {
allPaths.add(next);
return;
}
collect(node.left, next, allPaths);
collect(node.right, next, allPaths);
}
}class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
all_paths = []
self.collect(root, [], all_paths)
return [p for p in all_paths if sum(p) == targetSum]
def collect(self, node: Optional[TreeNode], path: List[int], all_paths: List[List[int]]) -> None:
if node is None:
return
nxt = path + [node.val]
if node.left is None and node.right is None:
all_paths.append(nxt)
return
self.collect(node.left, nxt, all_paths)
self.collect(node.right, nxt, all_paths)class Solution {
void collect(TreeNode* node, vector<int> path, vector<vector<int>>& allPaths) {
if (!node) return;
path.push_back(node->val);
if (!node->left && !node->right) {
allPaths.push_back(path);
return;
}
collect(node->left, path, allPaths);
collect(node->right, path, allPaths);
}
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> allPaths, res;
collect(root, {}, allPaths);
for (auto& p : allPaths) {
int sum = 0;
for (int v : p) sum += v;
if (sum == targetSum) res.push_back(p);
}
return res;
}
};function pathSum(root, targetSum) {
const allPaths = [];
collect(root, [], allPaths);
return allPaths.filter((p) => p.reduce((a, b) => a + b, 0) === targetSum);
}
function collect(node, path, allPaths) {
if (node === null) return;
const next = [...path, node.val];
if (node.left === null && node.right === null) {
allPaths.push(next);
return;
}
collect(node.left, next, allPaths);
collect(node.right, next, allPaths);
}2Optimal (DFS backtracking with remaining sum)
O(n + total length of the answer paths)Each node is entered and left once with O(1) work; copying happens only for the matching paths (in the worst case O(n · h) total).O(h)The shared path and the recursion stack are both as deep as the tree height h (not counting the output).Walk the tree once with a single shared path list and the sum still needed. Push the node's value on entry and pop it on exit, so path always holds the current root-to-node route. Only when a leaf brings the remaining sum to exactly 0 is the path copied into the answer.
- dfs(node, remain): if node is null, return.
- Append
node.valtopathand setremain -= node.val. - If node is a leaf and
remain == 0, add a copy ofpathto the answer. - Otherwise recurse into the left and right children with
remain. - Remove the last element of
pathbefore returning (backtrack).
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> res = new ArrayList<>();
dfs(root, targetSum, new ArrayList<>(), res);
return res;
}
private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
if (node == null) return;
path.add(node.val);
remain -= node.val;
if (node.left == null && node.right == null) {
if (remain == 0) res.add(new ArrayList<>(path));
} else {
dfs(node.left, remain, path, res);
dfs(node.right, remain, path, res);
}
path.remove(path.size() - 1);
}
}class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
self.dfs(root, targetSum, [], res)
return res
def dfs(self, node: Optional[TreeNode], remain: int, path: List[int], res: List[List[int]]) -> None:
if node is None:
return
path.append(node.val)
remain -= node.val
if node.left is None and node.right is None:
if remain == 0:
res.append(path[:])
else:
self.dfs(node.left, remain, path, res)
self.dfs(node.right, remain, path, res)
path.pop()class Solution {
void dfs(TreeNode* node, int remain, vector<int>& path, vector<vector<int>>& res) {
if (!node) return;
path.push_back(node->val);
remain -= node->val;
if (!node->left && !node->right) {
if (remain == 0) res.push_back(path);
} else {
dfs(node->left, remain, path, res);
dfs(node->right, remain, path, res);
}
path.pop_back();
}
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res;
vector<int> path;
dfs(root, targetSum, path, res);
return res;
}
};function pathSum(root, targetSum) {
const res = [];
const path = [];
function dfs(node, remain) {
if (node === null) return;
path.push(node.val);
remain -= node.val;
if (node.left === null && node.right === null) {
if (remain === 0) res.push([...path]);
} else {
dfs(node.left, remain);
dfs(node.right, remain);
}
path.pop();
}
dfs(root, targetSum);
return res;
}Edge cases to test
- Empty tree
- A single node equal (or not equal) to the target
- Negative values, so a partial sum can pass the target and come back
- A node with one child is not a leaf: the path must continue to a real leaf
- Several different leaves producing identical value lists
Hints
Hint 1
A path only counts if it ends at a leaf, a node with no children at all.
Hint 2
Walk the tree with DFS, carrying the remaining sum targetSum - (values so far).
Hint 3
Use one shared path list: add the node on the way down and remove it on the way back up (backtracking). Copy the path only when a leaf matches.
FAQ
What is the best time complexity for Path Sum II?
Optimal (DFS backtracking with remaining sum) runs in O(n + total length of the answer paths) time and O(h) extra space. Each node is entered and left once with O(1) work; copying happens only for the matching paths (in the worst case O(n · h) total).
Which pattern does Path Sum II use?
It is a trees & bst problem that uses the backtracking pattern. Other problems with the same pattern: Root to Leaf Paths, Path Sum III.
Is there a brute force solution for Path Sum II?
Yes. Brute force (collect every path, then filter) takes O(n · h) time and O(n · h) space. Generate every root-to-leaf path as its own fresh list (copying the path at each step), then keep the ones whose values add up to the target.
Which edge cases should I test for Path Sum II?
Empty tree; A single node equal (or not equal) to the target; Negative values, so a partial sum can pass the target and come back; A node with one child is not a leaf: the path must continue to a real leaf; Several different leaves producing identical value lists.