Count all downward paths in a binary tree whose values add up to a target, even when the path starts in the middle of the tree. Try it free and read the solution.

Path Sum III – Solve Online

Combination Sum III

Top K Frequent Words

Count all downward paths in a binary tree whose values add up to a target, even when the path starts in the middle of the tree.

Given the `root` of a binary tree and an integer `targetSum`, return the number of paths whose values add up to `targetSum`.

The path does **not** need to start at the root or end at a leaf, but it must move **downward only** (from parent to child along existing links).

**Input / output**
- Input: `root: TreeNode`, `targetSum: int` (the JSON test fixture for `root` is a LeetCode-style level-order array such as `[10,5,-3,3,2,null,11,3,-2,null,1]`, using `null` for missing children)
- Output: `int`

**Examples**
1. `root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8` returns `3`.
2. `root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22` returns `3`.
3. `root = [] , targetSum = 0` returns `0`.

**Constraints**
- `0 <= number of nodes <= 1000`
- `-10^9 <= Node.val <= 10^9`
- `-1000 <= targetSum <= 1000`

**Follow-up**
A brute-force DFS from every node works, but can you count all valid paths in a single traversal by combining a running prefix sum with a hash map of previously seen prefix sums?

- For each node, count how many downward paths starting exactly there sum to the remaining target.
- Then recurse into the left and right child as new starting points.
- This is easy to reason about and correct, but in a skewed tree it revisits many descendants for many different starts, so the worst-case time is `O(n^2)`.

Brute-force every possible starting node

- Track the running sum from the root to the current node.
- A path ending at the current node sums to `targetSum` whenever an earlier prefix sum equals `currentSum - targetSum`.
- Store counts of prefix sums in a hash map as you go down the tree, then **decrement that count while backtracking** so sibling paths do not accidentally reuse state from each other.
- This counts every valid downward path in `O(n)` time with `O(h)` recursion stack plus up to `O(n)` prefix-sum storage.

Use prefix sums plus a hash map for a single DFS

Example 1

Example 2