Path Sum

Problem

You are given the root of a binary tree and an integer targetSum. Determine whether the tree contains at least one root-to-leaf path whose node values add up exactly to targetSum. Return True if such a path exists, otherwise False.

A leaf is a node with no children. The path must start at the root and end at a leaf — it cannot stop partway down.

Examples

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 sums to 22.

Example 2

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

The two root-to-leaf paths sum to 1+2=3 and 1+3=4; neither is 5.

Example 3

Input: root = [], targetSum = 0
Output: False

An empty tree has no root-to-leaf paths at all, so the answer is False even for target 0.

Constraints

• The number of nodes is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

Node values can be negative, so you cannot prune a branch just because the running sum already exceeds the target.

Think about it first

TL;DR

DFS with a shrinking remaining target — O(n) time, O(h) space (h = tree height; O(n) worst case).

Approach 1 — Brute force: enumerate every root-to-leaf path

The naive idea is to collect every root-to-leaf path into a list of value-lists, then sum each one and check against the target.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional, List


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        paths: List[List[int]] = []

        def collect(node: Optional[TreeNode], path: List[int]) -> None:
            if not node:
                return
            path.append(node.val)
            if not node.left and not node.right:
                paths.append(path.copy())
            else:
                collect(node.left, path)
                collect(node.right, path)
            path.pop()

        collect(root, [])
        return any(sum(p) == targetSum for p in paths)

Complexity: O(n · h) time (each path is copied and re-summed), O(n · h) space for the stored paths. With n up to 5000 this actually passes, but storing every path just to sum it is pure waste — the running sum can be carried down the tree instead.

Approach 2 — DFS with remaining target (recursive)

The insight: you never need the whole path — only how much of the target is left. Subtract the node’s value as you descend; success means landing on a leaf with exactly its own value remaining. This is a plain depth-first search (DFS): explore one branch fully before backtracking.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        remaining = targetSum - root.val
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(
            root.right, remaining
        )

Walkthrough on Example 1 (targetSum = 22):

1. At root 5: not a leaf, recurse with remaining 22 − 5 = 17.
2. At 4 (left child): remaining 17 − 4 = 13.
3. At 11: remaining 13 − 11 = 2.
4. At 7 (leaf): 7 != 2 → False. Backtrack.
5. At 2 (leaf): 2 == 2 → True. The or chain propagates True all the way up.

Complexity: O(n) time — each node is visited once. O(h) space for the recursion stack, which is O(n) for a degenerate (linked-list-shaped) tree and O(log n) if balanced.

Approach 3 — Iterative DFS with an explicit stack

The insight: the recursion only carries one extra number per frame, so you can replace the call stack with your own stack of (node, remaining) pairs. Useful when the tree can be deep enough to overflow Python’s recursion limit (~1000 frames by default; 5000 nodes in a chain would blow it).

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        stack = [(root, targetSum)]
        while stack:
            node, remaining = stack.pop()
            if not node.left and not node.right and node.val == remaining:
                return True
            if node.right:
                stack.append((node.right, remaining - node.val))
            if node.left:
                stack.append((node.left, remaining - node.val))
        return False

Walkthrough on Example 2 (root = [1,2,3], targetSum = 5): pop (1, 5), push (3, 4) and (2, 4). Pop (2, 4): leaf, 2 != 4. Pop (3, 4): leaf, 3 != 4. Stack empty → False.

Complexity: O(n) time, O(h) space for the stack (O(n) worst case).

Common pitfalls

• Empty tree with target 0: hasPathSum(None, 0) must be False — there is no path, not a zero-sum one. Checking remaining == 0 at a null node gets this wrong and falsely accepts non-leaf stops.
• Stopping at internal nodes: the check must fire only at leaves (not node.left and not node.right), otherwise a partial path that happens to hit the target is wrongly accepted.
• Pruning on remaining < 0: tempting, but node values can be negative, so a path can dip below zero and recover.
• One-child nodes: a node with only a right child is not a leaf; recursing into a None left child must simply return False, not trigger a leaf check.

Pattern takeaway

Many tree problems reduce to: pass information down the tree as an argument (here, the remaining target) and combine boolean/numeric results up with or/and/min/max. When the per-node state is one small value, the recursive DFS converts mechanically into an iterative stack of (node, state) pairs — keep that translation in your pocket for deep trees.