[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

Thinking Process

1. Start from each node: Check all paths starting from each node
2. Current node check: If node value equals target, count it

• Trees have no cycles — recursion is natural.
• Combine results from left and right subtrees at each node.
• Base case is usually null; height drives stack space.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Recursive DFS (this problem)	O(n)	O(h) stack	Natural for trees and graphs
Iterative DFS (stack)	O(n)	O(n)	Avoid recursion depth limits
DFS with memoization	O(n)	O(n)	Overlapping subproblems on graphs
Backtracking DFS	O(2^n) typical	O(n)	Enumerate choices with pruning

Solution

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 {
        public 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);
    }
}

Solution Explanation

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:

// import java.util.*;
class Solution {
        public int dfs(TreeNode node, int targetSum, HashMap<long, int>& prefixSum, long currentSum) {
        if(!node) return 0;

        currentSum += node.val;
        int count = prefixSum[currentSum - targetSum];
        prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) + 1);

        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) {
        HashMap<long, int> prefixSum = new HashMap<long, int>();
        prefixSum.put(0, 1);
        return dfs = new return(root, targetSum, prefixSum, 0);
    }
}

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:

// import java.util.*;
class Solution {
        public int pathSum(TreeNode root, int targetSum) {
        if(!root) return 0;

        Deque<TreeNode> stk = new ArrayDeque<>();
        stk.offer(root);
        int count = 0;

        while(!stk.isEmpty()) {
            TreeNode node = stk.peek();
            stk.poll();

            count += dfs(node, targetSum);

            if(node.left) stk.offer(node.left);
            if(node.right) stk.offer(node.right);
        }

        return count;
    }
        public 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 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

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

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

Common Mistakes

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

5. Wrong path direction: Allowing paths to go upwards
6. Missing base cases: Not handling null nodes properly
7. Incorrect target update: Not subtracting current node value
8. 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

References

• LC 437: Path Sum III on LeetCode
• LeetCode Discuss — LC 437: Path Sum III
• LeetCode Editorial (may require premium)

Key Takeaways

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