Path Sum III — Solution in Python, Java & C++
Path Sum III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.
Path Sum III is a medium coding problem on hash table, depth-first search and trees, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Hash Table, Depth-First Search, Trees, Prefix Sum
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree and an integer targetSum, count the downward paths whose node values add up to targetSum.
A downward path is a sequence of one or more nodes in which each node is the child of the one before it. It may start at any node and end at any node below it (or at the same node) — it does not have to start at the root or end at a leaf.
Example 1
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: Three downward paths sum to 8: 5 → 3, 5 → 2 → 1, and -3 → 11.
Example 2
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Explanation: 5 → 4 → 11 → 2, 5 → 8 → 4 → 5, and 4 → 11 → 7 all sum to 22; a path need not start at the root.
Example 3
Input: root = [], targetSum = 0
Output: 0
Explanation: An empty tree has no paths.
Constraints
0 <= number of nodes <= 1000-10^9 <= Node.val <= 10^9-1000 <= targetSum <= 1000
Hints for Path Sum III
Hint 1
A downward path ending at a node is a suffix of the root-to-node path. Its sum is the difference of two prefix sums of that root path.
Hint 2
While walking down, keep how many times each prefix sum occurs on the current root path. At a node with running sum
S, the paths ending here that sum to the target correspond to earlier prefixes equal toS - targetSum.Hint 3
Start the counts with prefix 0 seen once, add the node's sum before visiting its children and remove it afterwards — the counts must describe only the current root path. Running sums need 64 bits.
How to solve Path Sum III
The sum of a downward path from u to v is prefix(v) - prefix(parent of u), prefix sums taken from the root. Counting, at every node, the earlier prefix sums on its root path that equal prefix(node) - targetSum counts every path exactly once.
Approach
- Keep a hash map
countsof prefix sums on the current root path, starting with{0: 1}(the empty prefix). - Visit a node with the running sum
Sof its parent: setS += node.val. - Add
counts[S - targetSum]to the answer — each such earlier prefix starts a path ending here with the target sum. - Increment
counts[S], visit both children withS, then decrementcounts[S]on the way back.
Why it works
Every downward path ends at exactly one node v and starts after exactly one earlier prefix on v's root path, so it is counted once, at v, by that prefix. Decrementing on exit keeps counts equal to the prefixes of the current root path only, so prefixes from other branches never pair up.
Complexity
- Time —
O(n) expected - Space —
O(h) for the map entries in use and the recursion
Pitfalls
- Values reach ±10^9 and a path holds up to 1000 of them: running sums overflow 32 bits.
- Forgetting the initial
{0: 1}misses the paths that start at the root. - Forgetting to decrement lets a prefix from a finished branch pair with nodes in another branch.
Reference solution
Python
from typing import Optional
def pathSum(root: Optional[TreeNode], targetSum: int) -> int:
counts = {0: 1}
def walk(node, running):
if node is None:
return 0
running += node.val
total = counts.get(running - targetSum, 0)
counts[running] = counts.get(running, 0) + 1
total += walk(node.left, running) + walk(node.right, running)
counts[running] -= 1
return total
return walk(root, 0)Java
public static int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> counts = new HashMap<>();
counts.put(0L, 1);
return prefixWalk(root, 0L, targetSum, counts);
}
static int prefixWalk(TreeNode node, long running, int targetSum, Map<Long, Integer> counts) {
if (node == null) return 0;
running += node.val;
int total = counts.getOrDefault(running - targetSum, 0);
counts.merge(running, 1, Integer::sum);
total += prefixWalk(node.left, running, targetSum, counts) + prefixWalk(node.right, running, targetSum, counts);
counts.merge(running, -1, Integer::sum);
return total;
}C++
int prefixWalk(TreeNode* node, long long running, int targetSum, unordered_map<long long, int>& counts);
int pathSum(TreeNode* root, int targetSum) {
unordered_map<long long, int> counts;
counts[0] = 1;
return prefixWalk(root, 0, targetSum, counts);
}
int prefixWalk(TreeNode* node, long long running, int targetSum, unordered_map<long long, int>& counts) {
if (!node) return 0;
running += node->val;
auto it = counts.find(running - targetSum);
int total = it == counts.end() ? 0 : it->second;
counts[running]++;
total += prefixWalk(node->left, running, targetSum, counts) + prefixWalk(node->right, running, targetSum, counts);
counts[running]--;
return total;
}JavaScript
var pathSum = function(root, targetSum) {
var counts = new Map();
counts.set(0, 1);
function walk(node, running) {
if (node === null) return 0;
running += node.val;
var total = counts.get(running - targetSum) || 0;
counts.set(running, (counts.get(running) || 0) + 1);
total += walk(node.left, running) + walk(node.right, running);
counts.set(running, counts.get(running) - 1);
return total;
}
return walk(root, 0);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 439 hash table problems · the whole catalogue
Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)