LeetCode 437 - Path Sum III

LeetCode Problem 437

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree and an integer targetSum. We need to count how many downward paths in the tree have values that add up exactly to targetSum.

A path can begin at any node and end at any node, as long as it always moves downward from parent to child. This is an important distinction because we are not restricted to paths that start at the root or end at a leaf. Every node in the tree can potentially serve as the starting point of a valid path.

For example, consider a path like:

5 -> 3

If the sum of those values equals the target, then it counts, even if the path does not start at the root.

The input is a standard binary tree where each node contains:

• An integer value
• A left child
• A right child

The output is a single integer representing the total number of valid downward paths whose sum equals targetSum.

The constraints are important:

• The tree contains at most 1000 nodes
• Node values can be negative
• Target values can also be negative

The presence of negative numbers means we cannot use techniques like sliding windows or greedy pruning. A path that currently exceeds the target might later become valid after adding negative values. Because of this, we need a more general approach.

Several edge cases immediately stand out:

• An empty tree should return 0
• Trees containing negative numbers may create many overlapping valid paths
• A single node may itself equal the target
• Multiple paths can overlap and share nodes
• Large positive and negative values mean we must rely on exact arithmetic rather than heuristics

These characteristics strongly suggest that this is fundamentally a prefix sum and DFS problem.

Approaches

Brute Force Approach

The brute-force strategy is to treat every node as a potential starting point. For each node, we recursively explore all downward paths beginning at that node and count how many produce the target sum.

The algorithm works like this:

1. Start DFS from every node in the tree.
2. During each DFS traversal, keep track of the remaining sum needed.
3. If the remaining sum becomes zero at any node, increment the answer.
4. Continue exploring left and right children.

This approach is correct because it explicitly examines every possible downward path in the tree.

However, it is inefficient because many paths are recomputed repeatedly. If the tree has N nodes, then for each node we may traverse almost the entire subtree below it.

In the worst case, such as a skewed tree, this leads to O(N^2) time complexity.

Optimal Approach

The key insight is that this problem resembles the classic "subarray sum equals k" problem for arrays.

Instead of recomputing every path separately, we can track prefix sums while traversing the tree.

Suppose:

• currentSum is the sum from the root to the current node
• We previously encountered a prefix sum currentSum - targetSum

Then the values between those two points must sum to targetSum.

This works because:

currentSum - previousPrefixSum = targetSum

Rearranging:

previousPrefixSum = currentSum - targetSum

So during DFS, we maintain a hash map that stores how many times each prefix sum has appeared along the current traversal path.

At every node:

• Compute the current prefix sum
• Check how many times currentSum - targetSum has occurred
• Add that count to the answer
• Store the current prefix sum before exploring children
• Remove it when backtracking

This allows us to count all valid paths in a single DFS traversal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²)	O(H)	Starts a DFS from every node
Optimal	O(N)	O(H) average, O(N) worst	Uses prefix sums with a hash map

H represents the height of the tree.

Algorithm Walkthrough

Optimal Prefix Sum DFS Algorithm

1. Initialize a hash map called prefixCount.

This map stores how many times a particular prefix sum has appeared along the current root-to-node path.

We begin with:

prefixCount[0] = 1

This is important because a path from the root itself may equal targetSum. 2. Start a depth-first traversal from the root.

During traversal, maintain a variable called currentSum, which represents the sum of all node values from the root to the current node. 3. At each node, update the running prefix sum.

currentSum += node.val

4. Determine how many valid paths end at the current node.

If we previously saw a prefix sum equal to:

currentSum - targetSum

then the segment between that earlier point and the current node sums to targetSum.

We add:

prefixCount[currentSum - targetSum]

to the answer. 5. Store the current prefix sum in the hash map.

This allows child nodes to use the current node as part of their path calculations. 6. Recursively explore the left and right subtrees.

Both children inherit the updated prefix sum information. 7. Backtrack after processing children.

Remove the current prefix sum from the map:

prefixCount[currentSum] -= 1

This step is crucial because paths must remain within the current traversal branch. Without backtracking, paths from unrelated branches could incorrectly combine. 8. Continue until all nodes are processed.

The accumulated count is the final answer.

Why it works

The algorithm maintains the invariant that prefixCount contains prefix sums only along the current root-to-node traversal path.

For every node, we check how many earlier prefix sums satisfy:

currentSum - previousPrefixSum = targetSum

Every such occurrence corresponds to a unique downward path ending at the current node whose sum equals the target.

Because every node is visited exactly once and every valid path is counted precisely when its endpoint is processed, the algorithm is both complete and correct.

Python Solution

from collections import defaultdict
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1

        def dfs(node: Optional[TreeNode], current_sum: int) -> int:
            if not node:
                return 0

            current_sum += node.val

            paths_found = prefix_count[current_sum - targetSum]

            prefix_count[current_sum] += 1

            paths_found += dfs(node.left, current_sum)
            paths_found += dfs(node.right, current_sum)

            prefix_count[current_sum] -= 1

            return paths_found

        return dfs(root, 0)

The implementation begins by creating a hash map called prefix_count. This stores the number of times each prefix sum appears along the current DFS path.

The line:

prefix_count[0] = 1

handles paths that start directly from the root.

The nested dfs function performs recursive traversal. Each call receives:

• The current node
• The running prefix sum

At each node:

current_sum += node.val

updates the running total.

We then determine how many valid paths end at the current node:

paths_found = prefix_count[current_sum - targetSum]

This works because any earlier prefix sum equal to current_sum - targetSum creates a valid path segment.

Next, we record the current prefix sum before traversing children:

prefix_count[current_sum] += 1

After recursively processing both subtrees, we backtrack:

prefix_count[current_sum] -= 1

This ensures sibling branches do not interfere with each other.

Finally, the DFS returns the total number of valid paths found in the subtree.

Go Solution

package main

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func pathSum(root *TreeNode, targetSum int) int {
	prefixCount := map[int]int{
		0: 1,
	}

	var dfs func(node *TreeNode, currentSum int) int

	dfs = func(node *TreeNode, currentSum int) int {
		if node == nil {
			return 0
		}

		currentSum += node.Val

		pathsFound := prefixCount[currentSum-targetSum]

		prefixCount[currentSum]++

		pathsFound += dfs(node.Left, currentSum)
		pathsFound += dfs(node.Right, currentSum)

		prefixCount[currentSum]--

		return pathsFound
	}

	return dfs(root, 0)
}

The Go implementation follows the exact same algorithmic structure as the Python solution.

A Go map[int]int is used instead of Python's defaultdict(int). Missing keys automatically return the zero value for integers, which makes the logic straightforward.

Nil nodes are checked explicitly:

if node == nil

Go integers are sufficient here because the constraints stay well within 64-bit limits on modern systems, though some implementations may choose int64 for extra safety.

The recursive DFS closure captures prefixCount and targetSum, allowing clean state management without global variables.

Worked Examples

Example 1

Input:

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

The valid paths are:

5 -> 3
5 -> 2 -> 1
-3 -> 11

Traversal Trace

Node	Current Sum	Needed Prefix	Matching Paths	Prefix Map After Insert
10	10	2	0	{0:1, 10:1}
5	15	7	0	{0:1, 10:1, 15:1}
3	18	10	1	{0:1, 10:1, 15:1, 18:1}
3	21	13	0	...
-2	16	8	0	...
2	17	9	0	...
1	18	10	1	...
-3	7	-1	0	...
11	18	10	1	...

At every node where currentSum - targetSum exists in the map, a valid path is found.

The final answer is:

3

Example 2

Input:

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

Valid paths:

5 -> 4 -> 11 -> 2
4 -> 11 -> 7
5 -> 8 -> 4 -> 5

Traversal Highlights

Node	Current Sum	Needed Prefix	Matches
5	5	-17	0
4	9	-13	0
11	20	-2	0
7	27	5	1
2	22	0	1
8	13	-9	0
4	17	-5	0
5	22	0	1

Total valid paths:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited exactly once
Space	O(H) average, O(N) worst	Hash map stores prefix sums along the current path

The DFS traversal processes each node exactly one time, and every hash map operation is O(1) on average.

The recursion depth equals the height of the tree. In a balanced tree this is O(log N), while in a skewed tree it becomes O(N).

The prefix sum map only stores sums along the active recursion path, so its size is bounded by the tree height.

Test Cases

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_example_1():
    return TreeNode(
        10,
        TreeNode(
            5,
            TreeNode(3, TreeNode(3), TreeNode(-2)),
            TreeNode(2, None, TreeNode(1)),
        ),
        TreeNode(-3, None, TreeNode(11)),
    )

def build_example_2():
    return TreeNode(
        5,
        TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
        TreeNode(8, TreeNode(13), TreeNode(4, TreeNode(5), TreeNode(1))),
    )

solution = Solution()

# Example 1 from problem statement
assert solution.pathSum(build_example_1(), 8) == 3

# Example 2 from problem statement
assert solution.pathSum(build_example_2(), 22) == 3

# Empty tree
assert solution.pathSum(None, 5) == 0

# Single node equals target
assert solution.pathSum(TreeNode(5), 5) == 1

# Single node does not equal target
assert solution.pathSum(TreeNode(5), 3) == 0

# Negative values
root = TreeNode(-2, None, TreeNode(-3))
assert solution.pathSum(root, -5) == 1

# Multiple overlapping paths
root = TreeNode(
    1,
    TreeNode(1, TreeNode(1), TreeNode(1)),
    TreeNode(1)
)
assert solution.pathSum(root, 2) == 4

# Path does not need to start at root
root = TreeNode(1, TreeNode(2, TreeNode(3)))
assert solution.pathSum(root, 5) == 1  # 2 -> 3

# Deep skewed tree
root = TreeNode(1)
current = root
for _ in range(4):
    current.right = TreeNode(1)
    current = current.right

assert solution.pathSum(root, 3) == 3

# Zero target with zero values
root = TreeNode(0, TreeNode(0), TreeNode(0))
assert solution.pathSum(root, 0) == 5

Test Summary

Test	Why
Example 1	Validates standard mixed-value tree
Example 2	Validates multiple valid paths
Empty tree	Ensures base case works
Single matching node	Tests minimal valid input
Single non-matching node	Tests minimal invalid input
Negative values	Confirms support for negatives
Overlapping paths	Ensures all valid paths are counted
Non-root starting path	Verifies paths can start anywhere
Skewed tree	Tests worst-case recursion depth
Zero target with zeros	Validates repeated prefix sums

Edge Cases

Empty Tree

An empty tree should immediately return 0 because there are no paths at all.

This case can easily cause null reference errors if recursion assumes every node exists. The implementation avoids this by checking:

if not node:
    return 0

before doing any processing.

Negative Numbers

Negative values are especially important because they invalidate pruning strategies.

For example, a path sum may temporarily exceed the target and later decrease due to a negative node. Algorithms that stop early when sums become too large would fail here.

The prefix sum approach works correctly regardless of positive or negative values because it relies purely on arithmetic differences between cumulative sums.

Paths Starting in the Middle of the Tree

A common mistake is assuming paths must begin at the root.

Consider:

1
 \
  2
   \
    3

with target 5.

The valid path is:

2 -> 3

The prefix sum technique naturally handles this because it detects valid subpaths between any two prefix sums along the current traversal path.

Duplicate Prefix Sums

When multiple nodes produce the same prefix sum, every occurrence matters.

For example, trees containing many zeros can generate repeated prefix sums. If the implementation stored only a boolean instead of a count, it would miss valid paths.

Using a frequency map ensures all matching paths are counted correctly.