What is the brute force approach and complexity for Path Sum III (prefix sum on a tree)?

For each node, DFS downward and count paths that hit the target with time complexity O(N²) and space complexity O(H).

What is the optimal approach and complexity for Path Sum III (prefix sum on a tree)?

DFS with a map of path prefixes: ans += seen[cur − target], insert, recurse, undo with optimal time complexity O(N) and space complexity O(N).

Path Sum III (prefix sum on a tree)

Q: How do you identify the pattern for Path Sum III (prefix sum on a tree)?

Look for key signals in the prompt: "path goes downward (parent to child)" indicates Each root-to-node path is an array, and a valid path is a contiguous piece of it.; "start and end anywhere" indicates Not root-to-leaf — any subarray of the path, so prefix differences, not a single running sum check.; "sum equals targetSum" indicates Exact target → look up `cur − target` in a map of counts.; "values can be negative" indicates No pruning when the sum gets big; prefix sums still work..

Medium·LeetCode #437 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given the root of a binary tree and a number targetSum.

Count the downward paths whose node values add up to targetSum. A path can start at any node and end at any node below it, but it must only go from parent to child. It does not have to start at the root or end at a leaf.

Input

The root of a binary tree (it may be empty) and an integer targetSum. Node values can be negative.

Output

The number of downward paths with sum targetSum.

Example 1

Input: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8

Output: 3

The paths are 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

The paths are 5 → 4 → 11 → 2, 5 → 8 → 4 → 5 and 4 → 11 → 7.

Constraints

• 0 ≤ number of nodes ≤ 1000
• −10^9 ≤ Node.val ≤ 10^9
• −1000 ≤ targetSum ≤ 1000
• Path sums can exceed the int range — use long long.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“path goes downward (parent to child)”

→ Each root-to-node path is an array, and a valid path is a contiguous piece of it.

“start and end anywhere”

→ Not root-to-leaf — any subarray of the path, so prefix differences, not a single running sum check.

“sum equals targetSum”

→ Exact target → look up `cur − target` in a map of counts.

“values can be negative”

→ No pruning when the sum gets big; prefix sums still work.

Approach Complexity Ladder

Brute Force — start a walk from every nodeO(N²)O(H)

For each node, DFS downward and count paths that hit the target

Optimal — prefix sums on the current pathO(N)O(N)

DFS with a map of path prefixes: ans += seen[cur − target], insert, recurse, undo

Brute Force Intuition

Any path has a top node. So for every node, walk down through its whole subtree, keeping a running sum, and count each time the sum equals the target. Then do the same for every other node.

Recognition rule for this sub-pattern:

Contiguous + exact sum, negatives allowed. Store how many times each prefix sum appeared; look up prefix − K.

Remember this · Prefix Sum

Trigger

Range sums, "subarray sum equals K" (especially with negatives), equal counts, divisible by K.

Think

If I knew the total up to every index, would the answer become a difference of two totals?

Key question

Which earlier prefix value am I looking for when I stand at index i?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Prefix Sum translate into production architectures and low-level memory mechanics.

LLD Architecture