What is the brute force approach and complexity for Path Sum?

Store the sum of every root-to-leaf path in a list, then look for the target with time complexity O(N) and space complexity O(N).

What is the optimal approach and complexity for Path Sum?

Subtract each node's value on the way down; only a leaf checks for exactly 0 with optimal time complexity O(N) and space complexity O(H).

How do you identify the pattern for Path Sum?

Look for key signals in the prompt: "root-to-leaf path" indicates The path starts at the root and ends at a leaf. So the check happens only at leaves, and the state flows top-down.; "adds up to targetSum" indicates An exact sum. Instead of adding from the root at each leaf, carry what is still missing down the tree.; "return true or false" indicates One matching path is enough, so the search can stop at the first success..

Path Sum

Easy·LeetCode #112Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTree DFS → Path state (top-down)

Complexity:O(N)→O(N)

Key Insight

Pass down the amount the rest of the path still has to reach: remaining = targetSum − node.val at each node. At a leaf, the path works exactly when remaining is 0. The || between the two children means one matching path is enough, so the search stops early.

Core Validity Invariant

A root-to-leaf path is a match when its remainder is exactly 0 at the leaf. Only a leaf can finish a path, so a node with one child is not an end.

Problem

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

A root-to-leaf path starts at the root and goes down one child at a time until it reaches a leaf. A leaf is a node with no children. Return true if at least one such path adds up to targetSum. Otherwise return false.

Input

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

Output

true if some root-to-leaf path has the target sum, otherwise false.

Example 1

Input: root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22

Output: true

The path 5 → 4 → 11 → 2 adds up to 22.

Example 2

Input: root = [1, 2, 3], targetSum = 5

Output: false

There are two root-to-leaf paths. 1 → 2 adds to 3, and 1 → 3 adds to 4. Neither is 5.

Example 3

Input: root = [], targetSum = 0

Output: false

An empty tree has no paths at all.

Constraints

• The tree has between 0 and 5000 nodes.
• −1000 ≤ Node.val ≤ 1000
• −1000 ≤ targetSum ≤ 1000

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A path must start at the root and end at a leaf. What is different about a node that has only one child?
2.
If I walk down and keep a running sum, what do I still need to know when I reach a node?
3.
Which node is allowed to decide the answer for a whole path?
4.
Can I stop early once the running sum is bigger than the target? Are all the values positive?
5.
What should the answer be for an empty tree?

Brute force approach

Idea

Walk the tree once and write down the sum of every root-to-leaf path in a list. When the walk is done, scan the list for targetSum. The sums are stored first and searched second, so the list holds one number per leaf.

Thinking process

1
The question is about whole root-to-leaf paths, so the simplest plan is to build all of them.
2
Walk the tree with a running sum. When we reach a leaf, the running sum is the sum of one full path, so add it to the list.
3
After every leaf is done, check the list for targetSum.
4
On the tree [1, 2, 3], the list becomes [3, 4], from the paths 1 → 2 and 1 → 3. Neither is 5, so the answer is false.

Code & Implementation

brute.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
    // Adds the sum of every root-to-leaf path to `sums`.
    void collect(TreeNode* node, int sum, vector<int>& sums) {
        if (!node) return;
        sum += node->val;
        if (!node->left && !node->right) {
            sums.push_back(sum);          // a leaf ends one full path
            return;
        }
        collect(node->left, sum, sums);
        collect(node->right, sum, sums);
    }

public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        vector<int> sums;
        collect(root, 0, sums);           // step 1: the sum of every path
        for (int s : sums)                // step 2: search the list
            if (s == targetSum) return true;
        return false;
    }
};

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // Adds the sum of every root-to-leaf path to `sums`.
    private void collect(TreeNode node, int sum, List<Integer> sums) {
        if (node == null) return;
        sum += node.val;
        if (node.left == null && node.right == null) {
            sums.add(sum); // a leaf ends one full path
            return;
        }
        collect(node.left, sum, sums);
        collect(node.right, sum, sums);
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> sums = new ArrayList<>();
        collect(root, 0, sums); // step 1: the sum of every path
        for (int s : sums) {    // step 2: search the list
            if (s == targetSum) return true;
        }
        return false;
    }
}

from typing import Optional, List, Dict, Tuple

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    # Adds the sum of every root-to-leaf path to `sums`.
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        sums: List[int] = []

        def collect(node: Optional[TreeNode], s: int) -> None:
            if not node:
                return
            s += node.val
            if not node.left and not node.right:
                sums.append(s)  # a leaf ends one full path
                return
            collect(node.left, s)
            collect(node.right, s)

        collect(root, 0)  # step 1: the sum of every path
        for s in sums:     # step 2: search the list
            if s == targetSum:
                return True
        return False

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

// Adds the sum of every root-to-leaf path to `sums`.
function collect(node: TreeNode | null, sum: number, sums: number[]): void {
    if (!node) return;
    sum += node.val;
    if (!node.left && !node.right) {
        sums.push(sum); // a leaf ends one full path
        return;
    }
    collect(node.left, sum, sums);
    collect(node.right, sum, sums);
}

export function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    const sums: number[] = [];
    collect(root, 0, sums); // step 1: the sum of every path
    for (const s of sums) { // step 2: search the list
        if (s === targetSum) return true;
    }
    return false;
}

Complexity

Time O(N)Space O(N)

Both approaches visit every node once, so both take O(N) time. The brute force also stores one sum per leaf, which can be about N / 2 numbers. The optimal keeps no list. It only uses the recursion stack, O(H), and it stops at the first match.

Optimized approach

Idea

Start from brute force

Brute force stores every path sum and then searches the list. But each stored sum is only needed to answer one question: is it equal to the target? That question can be asked at the leaf, so the sum never has to be stored.

Find the repeated work

The list is written once and read once, so it is extra work and extra memory. A path's remaining amount can be passed down instead. It already includes everything above the node.

Define the state — what variables do I need?

targetSum (parameter): The sum that the path from this node down to a leaf must still reach. At the root it is the full target.
remaining: targetSum minus this node's value. It is what the children's paths must add up to.

Define validity

A root-to-leaf path is a match when its remainder is exactly 0 at the leaf. Only a leaf can finish a path, so a node with one child is not an end.

Define the transitions — when does each pointer move, and why is it safe?

Enter a node

remaining = targetSum − node.val

The node's value is now used up. The children only have to make up the rest.

At a leaf (no children)

return remaining == 0

A leaf is the only place where a path ends. The path is an answer exactly when nothing is left over.

At a node with children

return hasPathSum(left, remaining) || hasPathSum(right, remaining)

One matching path is enough, so || stops the search at the first success.

What does the current window add to the answer?

Nothing is stored. Each node passes remaining down, and each leaf answers for the one path that reached it.

Code & Implementation

optimal.cpp

// struct TreeNode { int val; TreeNode *left; TreeNode *right; };  (given by LeetCode)
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (!root) return false;                    // empty tree: no path at all
        // What the rest of the path (below this node) must add up to.
        int remaining = targetSum - root->val;
        // Only a leaf can finish a path. A node with one child is not an end.
        if (!root->left && !root->right)
            return remaining == 0;
        return hasPathSum(root->left, remaining) || hasPathSum(root->right, remaining);
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false; // empty tree: no path at all
        // What the rest of the path (below this node) must add up to.
        int remaining = targetSum - root.val;
        // Only a leaf can finish a path. A node with one child is not an end.
        if (root.left == null && root.right == null)
            return remaining == 0;
        return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
    }
}

from typing import Optional, List, Dict, Tuple

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False  # empty tree: no path at all
        # What the rest of the path (below this node) must add up to.
        remaining = targetSum - root.val
        # Only a leaf can finish a path. A node with one child is not an end.
        if not root.left and not root.right:
            return remaining == 0
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)

export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

export function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
    if (!root) return false; // empty tree: no path at all
    // What the rest of the path (below this node) must add up to.
    const remaining = targetSum - root.val;
    // Only a leaf can finish a path. A node with one child is not an end.
    if (!root.left && !root.right)
        return remaining === 0;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

Complexity

Time O(N)Space O(H)

Each node is visited at most once. The space is the recursion depth H, the height of the tree, not the number of leaves. For a chain, H = N.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Store the sum of every root-to-leaf path in a list, then look for the target	O(N)	O(N)
Optimal	Subtract each node's value on the way down; only a leaf checks for exactly 0	O(N)	O(H)

Why does this belong to this pattern?

Clues in the problem statement

“root-to-leaf path”The path starts at the root and ends at a leaf. So the check happens only at leaves, and the state flows top-down.
“adds up to targetSum”An exact sum. Instead of adding from the root at each leaf, carry what is still missing down the tree.
“return true or false”One matching path is enough, so the search can stop at the first success.

Top-down path+carry the remaining sum+check only at the leaf→Tree DFS → Path state (top-down)

The path has a fixed start (the root) and a fixed end type (a leaf). That is why one value carried down is enough: the remaining sum replaces the running total. This problem differs from its neighbours in the sub-pattern in one way: the answer is a yes or no, so the first match ends the search. Binary Tree Paths and Path Sum II need the whole path, not just its sum.

Don't make this mistake

Checking at a missing child instead of at a leaf

✗ if (!root) return remaining == 0;

✓ if (!root) return false; if (!root->left && !root->right) return remaining == 0;

A missing child is not the end of a path. On [1, 2] with target 1: the right child of 1 is missing, and the remaining amount there is 1 − 1 = 0, so the wrong version returns true. The only path is 1 → 2, which adds to 3, so the answer is false. The same bug on an empty tree with target 0 also returns true.

Pattern confusion: stopping early like a positive-only sum

✗ if (sum > targetSum) return false; // prune

✓ No early stop. Keep going until a leaf.

The sliding-window habit says: once the sum passes the target, it can only grow, so stop. That only works when every value is positive. Here values can be negative. On [3, -5, 2] with target -2: the path 3 → -5 adds to -2, which is the target. Stopping at the root (3 is already above -2) returns false. The right answer is true.

Accepting a path that stops before a leaf

✗ if (remaining == 0) return true; // checked at every node

✓ Check remaining == 0 only at a leaf.

A node with children is not the end of a path, even when the remaining amount is already 0. On [1, 2, 3] with target 1, the root alone adds to 1, so the wrong version returns true. The paths 1 → 2 (sum 3) and 1 → 3 (sum 4) both miss 1, so the answer is false.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

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 Tree DFS translate into production architectures and low-level memory mechanics.

LLD Architecture