Count Paths Whose Sum Equals a Target

medium tree dfs prefix sum

Problem

Count paths going downward (parent → child only, any start, any end) whose values sum to target. Carry a running prefix sum down the DFS; whenever prefix − target exists in a hash map of prefixes seen on the current root-to-node path, that many earlier prefixes complete a target path.

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

Output3

Paths: 5 → 3, 5 → 2 → 1?, 10 → -3 → 11 — three downward paths summing to 8 in this tree.

tree (level-order)

target

def path_sum_count(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 pathSumCount(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 pathSumCount(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 pathSumCount(TreeNode* root, int target) {
    seen_.clear(); seen_[0] = 1;
    count_ = 0; target_ = target;
    dfs(root, 0);
    return count_;
}

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