437. Path Sum III

Quick Identifier

• Topic: trees
• Pattern: Prefix sum on tree + Tree DFS
• Difficulty: Medium
• Companies: Amazon, Google, Microsoft, Meta, Apple
• Frequency: High
• LeetCode: 437

Quick Sights

• Time Complexity: O(n) from the optimal approach.
• Space Complexity: O(h) from the optimal approach.
• Core Mechanism: Given the root of a binary tree and an integer targetSum, return the number of downward paths (node→…→descendant, length ≥ 1) whose values sum to targetSum. Paths do not need to start at the root or end at a leaf.

Concept Explanation

Given the root of a binary tree and an integer targetSum, return the number of downward paths (node→…→descendant, length ≥ 1) whose values sum to targetSum. Paths do not need to start at the root or end at a leaf.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• Count paths with sum constraint on trees (vertical chains)
• Same “prefix sum ↔ complement” idea as arrays, but prefix is root-to-current on current DFS branch
• Must reset frequency map when unwinding (different branches share prefixes differently)

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Brute force — try every ancestor as start, DFS down — O(n²) on skew trees.
• Better — prefix hashmap per root-to-node path — O(n) time average if map ops O(1).
• Optimal — O(n) time / O(h) stack + map — DFS from root; map counts prefix sums; on exit decrement count for current prefix.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func pathSum(root *TreeNode, targetSum int) int {
	counts := map[int]int{0: 1}
	var walk func(*TreeNode, int) int
	walk = func(node *TreeNode, prefix int) int {
		if node == nil {
			return 0
		}
		prefix += node.Val
		ways := counts[prefix-targetSum]
		counts[prefix]++
		ways += walk(node.Left, prefix) + walk(node.Right, prefix)
		counts[prefix]--
		return ways
	}
	return walk(root, 0)
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function pathSum(root, targetSum) {
	const counts = new Map([[0, 1]]);
	function walk(node, prefix) {
		if (node === null) {
			return 0;
		}
		prefix += node.val;
		let ways = counts.get(prefix - targetSum);
		if (ways === undefined) {
			ways = 0;
		}
		counts.set(prefix, (counts.get(prefix) ?? 0) + 1);
		ways += walk(node.left, prefix) + walk(node.right, prefix);
		counts.set(prefix, counts.get(prefix) - 1);
		return ways;
	}
	return walk(root, 0);
}

Walkthrough

Let targetSum = 8. Suppose along one downward walk prefixes hit {0:1, 5:1, 8:1} when prefix becomes 8: counts[8-8]=counts[0]=1 records one path ending at the current node. If a child later also reaches prefix=8, you may count another path that started below the original root of the subcall—map updates on the recursion stack keep branch-local history.

Invariant: counts only tracks prefix frequencies on the active path from the global root; post-order cleanup keeps cousin subtrees from sharing prefix state incorrectly.

Edge Cases

• Negative values — cannot prune by monotonicity; map approach still correct
• Zero target — multiple overlaps possible; map counts handle multiplicity
• targetSum equals single node value — path length 1

Pitfalls

• Forgetting counts[0]=1 baseline (empty prefix before root)
• Not undoing counts[prefix]++ after processing node (breaks sibling paths)

Similar Problems

• 113. Path Sum II — enumerate paths with exact root-to-leaf constraint.
• 1448. Count Good Nodes in Binary Tree — another path-value aggregation down from the root.
• 543. Diameter of Binary Tree — different path statistic, still “paths in tree” practice.

Variants

• Path must start at root or end at leaf only — tighter constraints, often simpler DFS.
• Path Sum I style existence check — boolean DFS without counting multiplicity.

Mind-Map Tags

#trees #prefix-sum #hashmap #backtrack-unwind #path-count