The Path Sum III problem counts the number of paths in a binary tree that sum to a target, where paths can start and end at any node (not just root-to-leaf) but must go downward. This coding problem uses the prefix sum technique on tree paths — extending the array prefix sum pattern to DFS traversal. The DFS, binary tree, and tree interview pattern is the core.
Apple, Goldman Sachs, Microsoft, Meta, Amazon, TikTok, Google, and Bloomberg ask this because it demonstrates the powerful "prefix sum on tree paths" technique. The ability to generalize array prefix sums to trees separates strong candidates from average ones.
DFS with prefix sum hash map. Maintain a hash map of prefix_sum → frequency along the current root-to-node path. At each node: compute new prefix sum = prev_prefix + node.val. Count paths ending here: map[prefix_sum - target]. Update map, recurse on children, undo map update on backtrack.
Tree: 10→(5→(3→(3,-2),2→(None,1)),-3→(None,11)). target=8. DFS paths with sum 8: (5→3), (5→2→1), (-3→11). Count = 3. Prefix sum approach: initialize map={0:1}. At node 10: sum=10, count+=map[10-8]=map[2]=0. At node 5: sum=15, count+=map[15-8]=map[7]=0. At node 3: sum=18, count+=map[10]=1... Continue for all paths.
Path Sum III's prefix-sum-on-trees technique is highly reusable. The critical steps: (1) init map with {0:1}, (2) at each node: query map[prefix_sum - target], add prefix_sum to map, recurse, undo map addition. The "undo" step is critical to avoid pollution of sibling paths. Practice this on "number of paths with sum k in a tree" and similar tree range-query problems.
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Lowest Common Ancestor of a Binary Tree | Medium | Solve | |
| Distribute Coins in Binary Tree | Medium | Solve | |
| Sum Root to Leaf Numbers | Medium | Solve | |
| Boundary of Binary Tree | Medium | Solve | |
| Binary Tree Longest Consecutive Sequence | Medium | Solve |
