Path Sum III

medium tree dfs prefix sum

Problem

You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

Inputtree = [10, 5, -3, 3, 2, _, 11, 3, -2, _, 1], target = 8

Output3

Paths: 5 → 3, 5 → 2 → 1, -3 → 11 — three downward paths summing to 8.

tree (level-order)

target

def path_sum(root, target):
    seen = {0: 1}
    count = 0
    def dfs(n, s):
        nonlocal count
        if not n: return
        s += n.val
        count += seen.get(s - target, 0)
        seen[s] = seen.get(s, 0) + 1
        dfs(n.left, s); dfs(n.right, s)
        seen[s] -= 1
    dfs(root, 0)
    return count

function pathSum(root, target) {
  const seen = new Map(); seen.set(0, 1);
  let count = 0;
  function dfs(n, sum) {
    if (!n) return;
    sum += n.val;
    count += seen.get(sum - target) || 0;
    seen.set(sum, (seen.get(sum) || 0) + 1);
    dfs(n.left, sum); dfs(n.right, sum);
    seen.set(sum, seen.get(sum) - 1);
  }
  dfs(root, 0);
  return count;
}

class Solution {
    int count;
    Map<Long, Integer> seen;
    int target;
    public int pathSum(TreeNode root, int target) {
        seen = new HashMap<>();
        seen.put(0L, 1);
        count = 0;
        this.target = target;
        dfs(root, 0L);
        return count;
    }
    private void dfs(TreeNode n, long sum) {
        if (n == null) return;
        sum += n.val;
        count += seen.getOrDefault(sum - target, 0);
        seen.merge(sum, 1, Integer::sum);
        dfs(n.left, sum); dfs(n.right, sum);
        seen.merge(sum, -1, Integer::sum);
    }
}

int count_;
unordered_map<long long, int> seen_;
int target_;
void dfs(TreeNode* n, long long sum) {
    if (!n) return;
    sum += n->val;
    auto it = seen_.find(sum - target_);
    count_ += it == seen_.end() ? 0 : it->second;
    seen_[sum]++;
    dfs(n->left, sum); dfs(n->right, sum);
    seen_[sum]--;
}
int pathSum(TreeNode* root, int target) {
    seen_.clear(); seen_[0] = 1;
    count_ = 0; target_ = target;
    dfs(root, 0);
    return count_;
}

Explanation

Here the path can start and end anywhere as long as it goes downward, which sounds expensive. The slick trick is a running prefix sum combined with a hash map, the same idea used for "subarray sums equal to k" — just applied along a root-to-node chain.

As we DFS, s holds the sum of values from the root down to the current node. A downward path ending here with value target exists for every earlier ancestor whose prefix sum was s - target. So we ask the map seen how many times s - target has occurred and add that to count.

Before recursing into children we record the current prefix by doing seen[s] += 1. After both children return, we undo it with seen[s] -= 1 so the count only reflects ancestors on the current path, not unrelated branches.

The map starts with {0: 1} so that a path beginning right at the root is counted correctly.

Example: target 8 finds 5 → 3, 5 → 2 → 1, and -3 → 11 — three downward paths summing to 8, so the answer is 3.

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