Path Sum III

Ishaan S Published 24 Oct, 2026

You are given the root of a binary tree and an integer targetSum. Count the downward paths whose node values add up to exactly targetSum.

A downward path is a sequence of one or more nodes in which every node is the parent of the next one. It may start at any node, not only the root, and may stop at any node, not only a leaf, but it can never go back up toward the root.

Node values may be negative or zero, so several different paths can share nodes and still count separately.

The tree is given as a level-order array in which null marks a missing child.

Example 1

Input: root = [3,1,-2,2,4,null,5], targetSum = 3 Output: 3 Why: Three downward paths add up to 3: the single node 3, the path 1 → 2, and the path -2 → 5.

Example 2

Input: root = [0,0,null,0], targetSum = 0 Output: 6 Why: Every single node equal to 0 counts, and so does every downward run of zeros: with three zeros in a line there are 6 paths.

Example 3

Input: root = [5], targetSum = 7 Output: 0 Why: The only node is 5, which does not equal 7.

Constraints

The number of nodes is between 0 and 1000.
-10⁹ <= Node.val <= 10⁹
-1000 <= targetSum <= 1000

Pattern Path · Trees: DFS · problem 90 of 169

The simple version: for every node, walk down from it and count how many prefixes of the walk hit the target. What does that cost on a long, thin tree?

Think of the values along the root-to-current-node route as an array. A downward path ending at the current node is a contiguous piece of that array.

With running sums from the root, the piece from just after ancestor A down to the current node sums to running - prefix(A). Keep a count of the prefix sums on the current route in a hash map.

Look up running - targetSum before descending, add the current sum to the map, recurse, then remove it on the way back up so other branches do not see it.

Target: O(n) time, O(n) extra space.

Start simple

Start a depth-first walk from every node and count how many partial sums along each walk equal the target: O(n·h) time, which is O(n²) for a skewed tree.

The key idea

Fix the node where a path ends. The route from the root to that node is a simple list of values, and every downward path ending there is a suffix of that list. This turns the tree problem into the classic "count subarrays with a given sum" problem, applied along each root-to-node route.

Let running be the sum from the root to the current node. A path starting just below some ancestor whose prefix sum is p has sum running - p, so it equals the target exactly when p = running - targetSum. A hash map from prefix sum to how many times it appears on the current route answers "how many such ancestors are there?" in O(1). Seeding the map with {0: 1} accounts for paths that start at the root.

During the depth-first search, add the current prefix sum to the map before visiting the children and remove it afterwards. That backtracking step keeps the map describing only the current root-to-node route, so a path can never jump between sibling branches.

Every node is visited once with O(1) map work, giving linear time.

Complexity

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

Python

from collections import defaultdict

class Solution:
    def pathSum(self, root, targetSum):
        # How many times each prefix sum occurs on the current root-to-node route.
        prefix_counts = defaultdict(int)
        prefix_counts[0] = 1                  # the empty prefix, for paths starting at the root

        def dfs(node, running):
            if node is None:
                return 0
            running += node.val
            # Paths ending here start right after an ancestor whose prefix is running - targetSum.
            count = prefix_counts[running - targetSum]
            prefix_counts[running] += 1
            count += dfs(node.left, running) + dfs(node.right, running)
            prefix_counts[running] -= 1       # leave this branch: forget its prefix
            return count

        return dfs(root, 0)

JavaScript

var pathSum = function(root, targetSum) {
  // How many times each prefix sum occurs on the current root-to-node route.
  const prefixCounts = new Map([[0, 1]]);

  const dfs = (node, running) => {
    if (node === null) return 0;
    running += node.val;
    // Paths ending here start right after an ancestor whose prefix is running - targetSum.
    let count = prefixCounts.get(running - targetSum) || 0;
    prefixCounts.set(running, (prefixCounts.get(running) || 0) + 1);
    count += dfs(node.left, running) + dfs(node.right, running);
    prefixCounts.set(running, prefixCounts.get(running) - 1);  // leave this branch
    return count;
  };

  return dfs(root, 0);
};

What the interviewer is checking

It tests whether you can recognise the prefix-sum-plus-hash-map trick in a new setting and handle the backtracking that keeps the state scoped to one branch.

Mistakes to avoid

Forgetting to seed the map with prefix sum 0, which misses paths that start at the root.
Not removing the current prefix sum after visiting the children, so sums leak into sibling subtrees.
Stopping a walk as soon as the target is reached; with zeros and negatives, longer paths may hit the target again.
Overflowing 32-bit integers in Java or C++: sums of values up to 10⁹ need 64-bit types.

Follow-ups to expect

Can you also return the paths themselves? (Store ancestor lists, output-sensitive cost.)
What if paths could bend through a parent? (Combine left and right sums per node.)
How would you avoid deep recursion? (Iterative DFS with explicit stack.)

In real software

Running totals with a lookup of earlier totals power queries such as "how many periods in this history had net change X", for example in financial ledgers or hierarchical cost reports.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

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

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;
        while (i < a.length) {
            TreeNode node = q.poll();
            if (i < a.length && a[i] != null) { node.left = new TreeNode(a[i]); q.add(node.left); }
            i++;
            if (i < a.length && a[i] != null) { node.right = new TreeNode(a[i]); q.add(node.right); }
            i++;
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{3, 1, -2, 2, 4, null, 5});
        System.out.println(new Solution().pathSum(root, 3)); // 3
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

const int NIL = INT_MIN;  // marks a missing child in the level-order array

// Builds a tree from a level-order array.
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == NIL) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (i < a.size()) {
        TreeNode* node = q.front(); q.pop();
        if (i < a.size() && a[i] != NIL) { node->left = new TreeNode(a[i]); q.push(node->left); }
        i++;
        if (i < a.size() && a[i] != NIL) { node->right = new TreeNode(a[i]); q.push(node->right); }
        i++;
    }
    return root;
}

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        return 0;
    }
};

int main() {
    TreeNode* root = build({3, 1, -2, 2, 4, NIL, 5});
    cout << Solution().pathSum(root, 3) << '\n';  // 3
}

Topics #090 #t-tree-dfs DFS Hash Table Medium Practice Tree