Path Sum III
Path Sum III is a medium trees & bst problem solved with the backtracking pattern.
The best approach, optimal (prefix sums on the current path), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (start a walk at every node) up.
Problem
Given the root of a binary tree and an integer targetSum, count the paths whose node values add up to targetSum.
A path may start and end at any nodes, but it must go downward only, from a parent to one of its children at each step. A single node is also a path.
Examples
Example 1
- Input
root = [4,2,6,-3,null,0,1], targetSum = 6- Output
3- Why
- The paths 4 → 2, the single node 6, and 6 → 0 each add up to 6.
Example 2
- Input
root = [1,-1,1,null,2], targetSum = 1- Output
3- Why
- The root on its own, the right child on its own, and -1 → 2 each sum to 1. The path 1 → -1 → 2 sums to 2 and does not count.
Example 3
- Input
root = [], targetSum = 0- Output
0- Why
- An empty tree has no paths at all.
Constraints
- The number of nodes is in the range
[0, 1000]. -10^9 <= Node.val <= 10^9-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 (start a walk at every node) | O(n · h), O(n²) worst case | O(h) |
| Optimal (prefix sums on the current path) | O(n) | O(n) |
1Brute force (start a walk at every node)
O(n · h), O(n²) worst caseEach node starts a walk over its subtree; a node is visited once per ancestor, so n · h in total.O(h)Recursion depth equals the tree height h.Treat every node as the top of a path. From it, walk down every branch keeping a running sum and count the nodes where the sum equals the target. Do this for all nodes.
- pathSum(node) = countFrom(node, 0) + pathSum(node.left) + pathSum(node.right), with 0 for an empty tree.
- countFrom(node, sum): sum += node.val; result = (sum == target ? 1 : 0) + countFrom(left, sum) + countFrom(right, sum).
- Use 64-bit sums.
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
return countFrom(root, 0L, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}
private int countFrom(TreeNode node, long sum, int target) {
if (node == null) return 0;
sum += node.val;
return (sum == target ? 1 : 0) + countFrom(node.left, sum, target) + countFrom(node.right, sum, target);
}
}class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
def count_from(node: Optional[TreeNode], total: int) -> int:
if node is None:
return 0
total += node.val
return (1 if total == targetSum else 0) + count_from(node.left, total) + count_from(node.right, total)
if root is None:
return 0
return count_from(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)class Solution {
int countFrom(TreeNode* node, long long sum, int target) {
if (!node) return 0;
sum += node->val;
return (sum == target ? 1 : 0) + countFrom(node->left, sum, target) + countFrom(node->right, sum, target);
}
public:
int pathSum(TreeNode* root, int targetSum) {
if (!root) return 0;
return countFrom(root, 0, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}
};function pathSum(root, targetSum) {
const countFrom = (node, sum) => {
if (!node) return 0;
sum += node.val;
return (sum === targetSum ? 1 : 0) + countFrom(node.left, sum) + countFrom(node.right, sum);
};
if (!root) return 0;
return countFrom(root, 0) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}2Optimal (prefix sums on the current path)
O(n)Every node is visited once with O(1) average hash-map work.O(n)The map holds at most h prefixes at a time, and the recursion is h deep; h can be n.Walk the tree once with DFS, carrying the prefix sum from the root to the current node. A downward path ending here sums to the target exactly when some ancestor's prefix equals prefix - target. A hash map counts the prefixes on the current root-to-node chain (seeded with 0 for the empty prefix). After finishing a node's children, decrement its prefix so sibling branches never see it.
- counts = {0: 1}.
- dfs(node, prefix): prefix += node.val; result = counts[prefix - target].
- counts[prefix]++, add dfs(left) and dfs(right), then counts[prefix]--.
- Return dfs(root, 0) (0 for an empty tree). Use 64-bit prefix sums.
class Solution {
private final Map<Long, Integer> counts = new HashMap<>();
public int pathSum(TreeNode root, int targetSum) {
counts.clear();
counts.put(0L, 1);
return dfs(root, 0L, targetSum);
}
private int dfs(TreeNode node, long prefix, int target) {
if (node == null) return 0;
prefix += node.val;
int result = counts.getOrDefault(prefix - target, 0);
counts.merge(prefix, 1, Integer::sum);
result += dfs(node.left, prefix, target) + dfs(node.right, prefix, target);
counts.merge(prefix, -1, Integer::sum);
return result;
}
}class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
counts = defaultdict(int)
counts[0] = 1
def dfs(node: Optional[TreeNode], prefix: int) -> int:
if node is None:
return 0
prefix += node.val
result = counts.get(prefix - targetSum, 0)
counts[prefix] += 1
result += dfs(node.left, prefix) + dfs(node.right, prefix)
counts[prefix] -= 1
return result
return dfs(root, 0)class Solution {
unordered_map<long long, int> counts;
int dfs(TreeNode* node, long long prefix, int target) {
if (!node) return 0;
prefix += node->val;
auto it = counts.find(prefix - target);
int result = it == counts.end() ? 0 : it->second;
counts[prefix]++;
result += dfs(node->left, prefix, target) + dfs(node->right, prefix, target);
counts[prefix]--;
return result;
}
public:
int pathSum(TreeNode* root, int targetSum) {
counts.clear();
counts[0] = 1;
return dfs(root, 0, targetSum);
}
};function pathSum(root, targetSum) {
const counts = new Map([[0, 1]]);
const dfs = (node, prefix) => {
if (!node) return 0;
prefix += node.val;
let result = counts.get(prefix - targetSum) ?? 0;
counts.set(prefix, (counts.get(prefix) ?? 0) + 1);
result += dfs(node.left, prefix) + dfs(node.right, prefix);
counts.set(prefix, counts.get(prefix) - 1);
return result;
};
return dfs(root, 0);
}Edge cases to test
- An empty tree (answer 0)
- Negative values, so a path can reach the target, go past it and come back
- Path sums that overflow a 32-bit integer
- Zero-valued nodes, which make several overlapping paths share the same sum
Hints
Hint 1
A path is fixed by its top node and its bottom node. Try every top node and walk down from it.
Hint 2
Along one root-to-node chain, a path ending at the current node has sum = prefix(current) - prefix(some ancestor).
Hint 3
Keep a hash map of how many times each prefix sum occurs on the current chain; remove the current prefix when you return from a node.
FAQ
What is the best time complexity for Path Sum III?
Optimal (prefix sums on the current path) runs in O(n) time and O(n) extra space. Every node is visited once with O(1) average hash-map work.
Which pattern does Path Sum III use?
It is a trees & bst problem that uses the backtracking pattern. Other problems with the same pattern: Root to Leaf Paths, Path Sum II.
Is there a brute force solution for Path Sum III?
Yes. Brute force (start a walk at every node) takes O(n · h), O(n²) worst case time and O(h) space. Treat every node as the top of a path.
Which edge cases should I test for Path Sum III?
An empty tree (answer 0); Negative values, so a path can reach the target, go past it and come back; Path sums that overflow a 32-bit integer; Zero-valued nodes, which make several overlapping paths share the same sum.