Log inSign up
mediumleetcodeNot Started

Path Sum III

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

Example 1 · Example 1: Multiple Internal Paths:

Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8 Tree: 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1
Output: 3
Explanation: Three paths sum to 8: 5 -> 3, 5 -> 2 -> 1, and -3 -> 11.

Example 2 · Example 2: Negative Numbers:

Input: root = [1, -2, -3], targetSum = -1 Tree: 1 / \ -2 -3
Output: 1
Explanation: Path 1 -> -2 sums to -1.

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Adapt 1D prefix sum hash table to tree branches.
  • Understand why backtracking map state is essential across branches.
  • Prevent 32-bit integer overflow when accumulating large node sums.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Downward path sum equals target.
  • Paths do not need to start at root or end at leaf.
  • Subarray sum equals K on a tree.

Algorithmic Decision Tree:

  • curSum += node.val.
  • count += prefixMap[curSum - targetSum].
  • prefixMap[curSum]++.
  • dfs(left); dfs(right).
  • prefixMap[curSum]-- (Backtrack).

Connected Patterns:

Subarray Sum Equals KPath SumPath Sum II

1. Double Recursion (Check From Every Node)

Intuition

1. Helper countFrom(node, sum): counts paths starting strictly at node. 2. Main pathSum(root, sum): return countFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum).

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Helper countFrom(node, rem): if null return 0; count = (node.val == rem) ? 1 : 0.
  2. Step 2: count += countFrom(node.left, rem - node.val) + countFrom(node.right, rem - node.val).
  3. Step 3: Main function: countFrom(root, target) + pathSum(root.left, target) + pathSum(root.right, target).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int countFrom(TreeNode* node, long long sum) {
9 if (!node) return 0;
10 int count = (node->val == sum) ? 1 : 0;
11 count += countFrom(node->left, sum - node->val);
12 count += countFrom(node->right, sum - node->val);
13 return count;
14 }
15public:
16 int pathSum(TreeNode* root, int targetSum) {
17 if (!root) return 0;
18 return countFrom(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
19 }
20};
21
22int main() {
23 // Sample driver execution
24 cout << "Execution completed successfully." << endl;
25 return 0;
26}
27

Time & Space Complexity

  • Time complexity: O(n^2) — On skewed trees, visits each subtree from every ancestor.
  • Space complexity: O(h) — Call stack bounded by tree height h.

2. Path Array Suffix Sum Check

Intuition

Push node.val to an array. Iterate backwards from current node summing values. If suffix sum equals targetSum, count++. Pop on backtrack.

When to apply: Intermediate solution without hash map.

Algorithm

  1. Step 1: Push node.val to path vector.
  2. Step 2: Loop backwards from end of vector, accumulating sum. If sum == targetSum, count++.
  3. Step 3: Recurse on children.
  4. Step 4: Pop node.val from path vector.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 int total = 0;
9 vector<int> path;
10 void dfs(TreeNode* node, int target) {
11 if (!node) return;
12 path.push_back(node->val);
13 long long sum = 0;
14 for (int i = (int)path.size() - 1; i >= 0; --i) {
15 sum += path[i];
16 if (sum == target) total++;
17 }
18 dfs(node->left, target);
19 dfs(node->right, target);
20 path.pop_back();
21 }
22public:
23 int pathSum(TreeNode* root, int targetSum) {
24 dfs(root, targetSum);
25 return total;
26 }
27};
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(n * h) — Loops backwards through path of length h for every node.
  • Space complexity: O(h) — Path vector and recursion stack take O(h) space.

3. Prefix Sum Hash Map with Backtracking (Strict O(n))

Intuition

Prefix sum on a tree. If prefixSum - targetSum exists in map, add its frequency. Increment map[prefixSum], recurse on left and right, and decrement map[prefixSum] before returning.

When to apply: Optimal gold-standard solution.

Algorithm

  1. Step 1: Initialize prefixMap with {0: 1}.
  2. Step 2: Helper dfs(node, curSum, target): if null return 0.
  3. Step 3: curSum += node.val.
  4. Step 4: paths = prefixMap[curSum - target].
  5. Step 5: prefixMap[curSum]++; paths += dfs(left) + dfs(right); prefixMap[curSum]--. Return paths.

Prefix Sum Trace for root = [10, 5], targetSum = 5

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Start at root 10
Visual state
Values and pointers at this exact step
tree
Root
10 (sum: 10)
L
5

Node order shown; add connections to display explicit tree edges.

sum: 10: 10
Check / comparison
Sum: 10, Needed: 5, Found: 0
Decision / next transition
Record sum 10 in map. Recurse to left child 5.
Why this step matters

Step 1: Start at root 10. prefixMap = {0: 1}. Running sum = 10. Check if (10 - 5 = 5) exists in map: No. Add 10 to map: {0: 1, 10: 1}.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 unordered_map<long long, int> prefixMap;
9 int dfs(TreeNode* node, long long curSum, int target) {
10 if (!node) return 0;
11 curSum += node->val;
12 int count = prefixMap[curSum - target];
13 prefixMap[curSum]++;
14 count += dfs(node->left, curSum, target);
15 count += dfs(node->right, curSum, target);
16 prefixMap[curSum]--;
17 return count;
18 }
19public:
20 int pathSum(TreeNode* root, int targetSum) {
21 prefixMap[0] = 1;
22 return dfs(root, 0, targetSum);
23 }
24};
25
26int main() {
27 // Sample driver execution
28 cout << "Execution completed successfully." << endl;
29 return 0;
30}
31

Time & Space Complexity

  • Time complexity: O(n) — Single traversal visiting each node once with O(1) hash map operations.
  • Space complexity: O(h) — Hash map contains at most h active prefix sums; recursion stack is O(h).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Double RecursionO(n^2)O(h)Starts a downward search from every node.Repeated subtree scans.
2.Suffix Sum in Path VectorO(n * h)O(h)Loop backwards from end of path vector.Backward path iteration.
3.Prefix Sum Hash Map with BacktrackingOptimalO(n)O(h)Hash table stores prefix sum counts; backtrack map state on return.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Empty tree: returns 0.
  • Large node values: use 64-bit integer (long long) for running sum.
  • targetSum = 0 with zero values: handled correctly by prefix map counts.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention the 64-bit overflow trap: node values up to 109 can cause running sums to overflow 32-bit signed integers.
  2. Contrast brute force (O(n2) double recursion) with prefix sum hash map (O(n) single pass).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the backtracking step prefixMap[curSum]-- mandatory when returning from a node's recursive call?

Back to DSA Sheet