Path Sum III

Medium
1918.

Path Sum III

Path Sum III is a medium coding problem on hash table, depth-first search and trees, asked in Amazon, Google and Meta interviews.

Given the root of a binary tree and an integer targetSum, count the downward paths whose node values add up to targetSum.

A downward path is a sequence of one or more nodes in which each node is the child of the one before it. It may start at any node and end at any node below it (or at the same node) — it does not have to start at the root or end at a leaf.

Example 1

Input
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output
3
Explanation
Three downward paths sum to 8: 5 → 3, 5 → 2 → 1, and -3 → 11.

Example 2

Input
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output
3
Explanation
5 → 4 → 11 → 2, 5 → 8 → 4 → 5, and 4 → 11 → 7 all sum to 22; a path need not start at the root.

Example 3

Input
root = [], targetSum = 0
Output
0
Explanation
An empty tree has no paths.

Constraints

  • 0 <= number of nodes <= 1000
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number}
 */
var pathSum = function(root, targetSum) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Path Sum III — Solution in Python, Java & C++

Path Sum III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Path Sum III is a medium coding problem on hash table, depth-first search and trees, asked in Amazon, Google and Meta interviews.

Problem statement

Given the root of a binary tree and an integer targetSum, count the downward paths whose node values add up to targetSum.

A downward path is a sequence of one or more nodes in which each node is the child of the one before it. It may start at any node and end at any node below it (or at the same node) — it does not have to start at the root or end at a leaf.

Example 1

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: Three downward paths sum to 8: 5 → 3, 5 → 2 → 1, and -3 → 11.

Example 2

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Explanation: 5 → 4 → 11 → 2, 5 → 8 → 4 → 5, and 4 → 11 → 7 all sum to 22; a path need not start at the root.

Example 3

Input: root = [], targetSum = 0
Output: 0
Explanation: An empty tree has no paths.

Constraints

  • 0 <= number of nodes <= 1000
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000

Hints for Path Sum III

  1. Hint 1

    A downward path ending at a node is a suffix of the root-to-node path. Its sum is the difference of two prefix sums of that root path.

  2. Hint 2

    While walking down, keep how many times each prefix sum occurs on the current root path. At a node with running sum S, the paths ending here that sum to the target correspond to earlier prefixes equal to S - targetSum.

  3. Hint 3

    Start the counts with prefix 0 seen once, add the node's sum before visiting its children and remove it afterwards — the counts must describe only the current root path. Running sums need 64 bits.

How to solve Path Sum III

The sum of a downward path from u to v is prefix(v) - prefix(parent of u), prefix sums taken from the root. Counting, at every node, the earlier prefix sums on its root path that equal prefix(node) - targetSum counts every path exactly once.

Approach

  1. Keep a hash map counts of prefix sums on the current root path, starting with {0: 1} (the empty prefix).
  2. Visit a node with the running sum S of its parent: set S += node.val.
  3. Add counts[S - targetSum] to the answer — each such earlier prefix starts a path ending here with the target sum.
  4. Increment counts[S], visit both children with S, then decrement counts[S] on the way back.

Why it works

Every downward path ends at exactly one node v and starts after exactly one earlier prefix on v's root path, so it is counted once, at v, by that prefix. Decrementing on exit keeps counts equal to the prefixes of the current root path only, so prefixes from other branches never pair up.

Complexity

  • Time — O(n) expected
  • Space — O(h) for the map entries in use and the recursion

Pitfalls

  • Values reach ±10^9 and a path holds up to 1000 of them: running sums overflow 32 bits.
  • Forgetting the initial {0: 1} misses the paths that start at the root.
  • Forgetting to decrement lets a prefix from a finished branch pair with nodes in another branch.

Reference solution

Python

from typing import Optional

def pathSum(root: Optional[TreeNode], targetSum: int) -> int:
    counts = {0: 1}

    def walk(node, running):
        if node is None:
            return 0
        running += node.val
        total = counts.get(running - targetSum, 0)
        counts[running] = counts.get(running, 0) + 1
        total += walk(node.left, running) + walk(node.right, running)
        counts[running] -= 1
        return total

    return walk(root, 0)

Java

public static int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> counts = new HashMap<>();
    counts.put(0L, 1);
    return prefixWalk(root, 0L, targetSum, counts);
}

static int prefixWalk(TreeNode node, long running, int targetSum, Map<Long, Integer> counts) {
    if (node == null) return 0;
    running += node.val;
    int total = counts.getOrDefault(running - targetSum, 0);
    counts.merge(running, 1, Integer::sum);
    total += prefixWalk(node.left, running, targetSum, counts) + prefixWalk(node.right, running, targetSum, counts);
    counts.merge(running, -1, Integer::sum);
    return total;
}

C++

int prefixWalk(TreeNode* node, long long running, int targetSum, unordered_map<long long, int>& counts);

int pathSum(TreeNode* root, int targetSum) {
    unordered_map<long long, int> counts;
    counts[0] = 1;
    return prefixWalk(root, 0, targetSum, counts);
}

int prefixWalk(TreeNode* node, long long running, int targetSum, unordered_map<long long, int>& counts) {
    if (!node) return 0;
    running += node->val;
    auto it = counts.find(running - targetSum);
    int total = it == counts.end() ? 0 : it->second;
    counts[running]++;
    total += prefixWalk(node->left, running, targetSum, counts) + prefixWalk(node->right, running, targetSum, counts);
    counts[running]--;
    return total;
}

JavaScript

var pathSum = function(root, targetSum) {
    var counts = new Map();
    counts.set(0, 1);
    function walk(node, running) {
        if (node === null) return 0;
        running += node.val;
        var total = counts.get(running - targetSum) || 0;
        counts.set(running, (counts.get(running) || 0) + 1);
        total += walk(node.left, running) + walk(node.right, running);
        counts.set(running, counts.get(running) - 1);
        return total;
    }
    return walk(root, 0);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 439 hash table problems · the whole catalogue

Learn the technique: Hashing: Hash Maps and Hash Sets · Depth-First Search (DFS)