[Medium] 437. Path Sum III

[Medium] 437. Path Sum III

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).

Examples

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are:
- Path 1: 10 → 5 → 3 = 18 (sum = 18)
- Path 2: 5 → 3 = 8 (sum = 8)
- Path 3: 5 → 2 → 1 = 8 (sum = 8)

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Explanation: The paths that sum to 22 are:
- Path 1: 5 → 4 → 11 → 2 = 22 (sum = 22)
- Path 2: 4 → 11 → 7 = 22 (sum = 22)
- Path 3: 5 → 8 → 4 → 5 = 22 (sum = 22)

Constraints

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

1. Path definition: What defines a valid path? (Assumption: Path from any node to any descendant node - doesn’t need to start at root or end at leaf)

2. Path sum calculation: How is path sum calculated? (Assumption: Sum of all node values along the path)

3. Return value: What should we return? (Assumption: Count of paths with sum equal to targetSum - integer)

4. Negative values: Can node values and targetSum be negative? (Assumption: Yes - per constraints, both can be negative)

5. Path direction: Can paths go upward in the tree? (Assumption: No - paths go downward from parent to child - standard tree path)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

Initial Thought: “I need to find paths with target sum. Let me check all possible paths.”

Naive Solution: For each node, check all paths starting from that node, count paths with target sum.

Complexity: O(n²) time, O(n) space

Issues:

• O(n²) time - checks many paths
• Repeats work for overlapping paths
• Doesn’t leverage prefix sum
• Can be optimized

Step 2: Semi-Optimized Approach (7 minutes)

Insight: “I can use DFS with prefix sum tracking. Track sum from root to current node.”

Improved Solution: Use DFS with prefix sum. For each node, check if any prefix sum difference equals target. Use hash map to track prefix sums.

Complexity: O(n) time, O(n) space

Improvements:

• Prefix sum enables efficient checking
• O(n) time - single DFS pass
• Hash map tracks prefix sums
• Handles all paths correctly

Step 3: Optimized Solution (8 minutes)

Final Optimization: “DFS with prefix sum hash map is optimal. Backtrack map updates.”

Best Solution: DFS with prefix sum hash map. Track running sum, check if (current_sum - target) exists in map. Backtrack map updates when leaving subtree.

Complexity: O(n) time, O(n) space

Key Realizations:

1. Prefix sum is key technique for path sum problems
2. Hash map enables O(1) lookup
3. O(n) time is optimal - visit each node once
4. Backtracking ensures correct counting

Solution: DFS with Recursion

Time Complexity: O(n²) where n is the number of nodes
Space Complexity: O(h) where h is the height of the tree

Use DFS to explore all possible paths starting from each node, checking if the path sum equals the target.

class Solution {
private:
    int dfs(TreeNode* node, int targetSum) {
        if(!node) return 0;
        int cnt = 0;
        if(targetSum == node->val) cnt++;
        return cnt + dfs(node->left, targetSum - node->val) + dfs(node->right, targetSum - node->val);
    }
    
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        return dfs(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }
};

How the Algorithm Works

Key Insight: For each node, check all paths starting from that node, then recursively check paths starting from its children.

Steps:

1. Base case: If root is null, return 0
2. DFS from current node: Count paths starting from current node
3. Recursive calls: Check paths starting from left and right children
4. Sum results: Return total count from all three sources

Step-by-Step Example

Example: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8

Tree Structure:

        10
       /  \
      5   -3
     / \    \
    3   2   11
   / \   \
  3  -2   1

DFS from each node:

Node	Target	Paths Found	Count
10	8	10→5→3 (18), 10→5→2→1 (18)	0
5	8	5→3 (8), 5→2→1 (8)	2
-3	8	-3→11 (8)	1
3	8	3 (3)	0
2	8	2→1 (3)	0
11	8	11 (11)	0
3	8	3 (3)	0
-2	8	-2 (-2)	0
1	8	1 (1)	0

Total count: 2 + 1 = 3

Algorithm Breakdown

DFS Function:

int dfs(TreeNode* node, int targetSum) {
    if(!node) return 0;
    int cnt = 0;
    if(targetSum == node->val) cnt++;
    return cnt + dfs(node->left, targetSum - node->val) + dfs(node->right, targetSum - node->val);
}

Process:

1. Base case: Return 0 if node is null
2. Check current node: If node value equals target, increment count
3. Recursive calls: Check left and right subtrees with updated target
4. Return total count from current node and subtrees

Main Function:

int pathSum(TreeNode* root, int targetSum) {
    if(!root) return 0;
    return dfs(root, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
}

Process:

1. Base case: Return 0 if root is null
2. DFS from root: Count paths starting from root
3. Recursive calls: Count paths starting from left and right subtrees
4. Return total count from all sources

Complexity Analysis

Operation	Time Complexity	Space Complexity
DFS from each node	O(n)	O(h)
Total DFS calls	O(n)	O(h)
Total	O(n²)	O(h)

Where n is the number of nodes and h is the height of the tree.

Edge Cases

1. Empty tree: root = null → 0
2. Single node: root = [5], targetSum = 5 → 1
3. No valid paths: root = [1,2,3], targetSum = 10 → 0
4. Negative values: root = [1,-2,3], targetSum = 1 → 2

Key Insights

DFS Approach:

1. Start from each node: Check all paths starting from each node
2. Path continuation: Paths can start from any node and go downwards
3. Target reduction: Subtract current node value from target
4. Recursive exploration: Explore all possible paths

Path Counting:

1. Current node check: If node value equals target, count it
2. Subtree exploration: Continue checking with updated target
3. Sum accumulation: Add counts from all subtrees
4. Complete coverage: Check all possible starting points

Detailed Example Walkthrough

Example: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

Tree Structure:

        5
       / \
      4   8
     /   / \
    11  13  4
   / \     / \
  7   2   5   1

DFS from each node:

Node	Target	Paths Found	Count
5	22	5→4→11→2 (22), 5→8→4→5 (22)	2
4	22	4→11→7 (22)	1
8	22	8→13 (21), 8→4→5 (17), 8→4→1 (13)	0
11	22	11→7 (18), 11→2 (13)	0
13	22	13 (13)	0
4	22	4→5 (9), 4→1 (5)	0
7	22	7 (7)	0
2	22	2 (2)	0
5	22	5 (5)	0
1	22	1 (1)	0

Total count: 2 + 1 = 3

Alternative Approaches

Approach 1: Prefix Sum with Hash Map

class Solution {
private:
    int dfs(TreeNode* node, int targetSum, unordered_map<long, int>& prefixSum, long currentSum) {
        if(!node) return 0;
        
        currentSum += node->val;
        int count = prefixSum[currentSum - targetSum];
        prefixSum[currentSum]++;
        
        count += dfs(node->left, targetSum, prefixSum, currentSum);
        count += dfs(node->right, targetSum, prefixSum, currentSum);
        
        prefixSum[currentSum]--;
        return count;
    }
    
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> prefixSum;
        prefixSum[0] = 1;
        return dfs(root, targetSum, prefixSum, 0);
    }
};

Time Complexity: O(n)
Space Complexity: O(n)

Approach 2: Iterative DFS

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root) return 0;
        
        stack<TreeNode*> stk;
        stk.push(root);
        int count = 0;
        
        while(!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            
            count += dfs(node, targetSum);
            
            if(node->left) stk.push(node->left);
            if(node->right) stk.push(node->right);
        }
        
        return count;
    }
    
private:
    int dfs(TreeNode* node, int targetSum) {
        if(!node) return 0;
        int cnt = 0;
        if(targetSum == node->val) cnt++;
        return cnt + dfs(node->left, targetSum - node->val) + dfs(node->right, targetSum - node->val);
    }
};

Time Complexity: O(n²)
Space Complexity: O(n)

Common Mistakes

1. Wrong path direction: Allowing paths to go upwards
2. Missing base cases: Not handling null nodes properly
3. Incorrect target update: Not subtracting current node value
4. Double counting: Counting same path multiple times

Related Problems

• 112. Path Sum
• 113. Path Sum II
• 124. Binary Tree Maximum Path Sum
• 257. Binary Tree Paths

Why This Solution Works

DFS Approach:

1. Complete coverage: Checks all possible starting points
2. Path continuation: Allows paths to start from any node
3. Target reduction: Properly updates target for subtrees
4. Recursive structure: Naturally handles tree traversal

Path Counting:

1. Current node check: Counts if current node equals target
2. Subtree exploration: Continues checking with updated target
3. Sum accumulation: Adds counts from all subtrees
4. Correct result: Produces accurate path count

Key Algorithm Properties:

1. Correctness: Always produces valid result
2. Completeness: Checks all possible paths
3. Efficiency: O(n²) time complexity
4. Simplicity: Easy to understand and implement