Path Sum III

MediumBinary Tree · DFS + Prefix Sum🧩 Tree DFS LeetCode #437 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree and an integer targetSum, count the downward paths whose node values add up to targetSum. A path may start and end at any nodes, but it must only travel from parent to child (it need not begin at the root or finish at a leaf).

Input[10,5,-3,3,2,null,11,3,-2,null,1], 8Output3

Input[5,4,8,11,null,13,4,7,2,null,null,5,1], 22Output3

0 ≤ n ≤ 1000 · -10⁹ ≤ Node.val ≤ 10⁹ · -1000 ≤ targetSum ≤ 1000

Try it yourself

Java

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

It is Subarray Sum Equals K on every root-to-node path. If prefix(node) - prefix(ancestor) == target, the segment below that ancestor is a valid path — so count earlier prefixes equal to cur - target in a hash map, and undo the map entry when backtracking.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceDouble DFS (Every Node as a Start)

Time O(n·h) → O(n²)Space O(h)

The outer DFS picks every node as a possible path start; the inner DFS walks down from it, subtracting values from the remaining target and counting each node where the remainder hits exactly the node value. Each node is re-walked once per ancestor, i.e. h times.

Java

public int pathSum(TreeNode root, int targetSum) {
    if (root == null) return 0;
    return countFrom(root, targetSum)
         + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}
// paths that start exactly at node
private int countFrom(TreeNode node, long remaining) { // long: values reach 1e9
    if (node == null) return 0;
    int count = node.val == remaining ? 1 : 0;
    remaining -= node.val;
    return count + countFrom(node.left, remaining) + countFrom(node.right, remaining);
}

Simple and correct; O(n log n) on balanced trees but O(n²) on a chain.

OptimalPrefix Sum + Hash Map with Backtracking

Time O(n)Space O(h)

One DFS keeps a running sum cur from the root and a map prefix sum → count for the nodes on the current path only (seeded with 0 → 1 for paths starting at the root). Paths ending here = map[cur - target]. After both children, decrement cur so sibling branches never see it.

Java

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> seen = new HashMap<>();
    seen.put(0L, 1); // empty prefix: path starting at the root
    return dfs(root, 0L, targetSum, seen);
}
private int dfs(TreeNode node, long cur, int target, Map<Long, Integer> seen) {
    if (node == null) return 0;
    cur += node.val;
    int count = seen.getOrDefault(cur - target, 0); // paths ending at node
    seen.merge(cur, 1, Integer::sum);
    count += dfs(node.left, cur, target, seen) + dfs(node.right, cur, target, seen);
    if (seen.merge(cur, -1, Integer::sum) == 0) seen.remove(cur); // backtrack
    return count;
}

Single pass with O(1) work per node — the interview-grade solution.

Pro tip

Query cur - target before inserting cur; otherwise target = 0 counts an empty path at every node.

At a glance

Level	Approach	Time	Space
Brute Force	Double DFS (Every Node as a Start)	`O(n·h) → O(n²)`	`O(h)`
Optimal	Prefix Sum + Hash Map with Backtracking	`O(n)`	`O(h)`

Common pitfalls

Using int sums — values up to 10⁹ overflow; use long.
Forgetting to backtrack the map — prefixes leak into sibling subtrees.
Stopping after the first match — negatives mean a longer path can hit the target again.

Interview tips

Link it to Subarray Sum Equals K (560) — same trick, on a tree path.
Explain the {0: 1} seed: it counts paths that start at the root.
State the brute force cost precisely: O(n·h), quadratic only on skewed trees.

Pattern

Prefix sum + hash map (with backtracking) → count sub-paths/subarrays summing to k, even with negatives.

My notes saved in this browser