Path Sum

A matching sum at an internal node is not enough. The path must start at the root, end at a leaf, and satisfy the target at that boundary.

The clean Path Sum solution is a depth-first search that carries one piece of state: the sum still required from the current node down to a leaf.

Read the contract before choosing DFS

You are given:

• root, the root of a binary tree
• targetSum, an integer

Return True if at least one root-to-leaf path has node values that add up to targetSum. Otherwise, return False.

A valid path must:

1. Start at the root.
2. Follow child links downward.
3. End at a leaf, meaning a node with no left or right child.

The leaf condition is the central boundary. If an internal node happens to make the sum equal targetSum, the path is still incomplete.

An empty tree has no root-to-leaf path, so it returns False.

Node values may be negative. Do not assume that a sum grows monotonically as you move down the tree. A later negative value can bring an oversized running sum back to the target.

The input allows up to 5,000 nodes. That makes a linear traversal the right goal.

Recognize the root-to-leaf DFS pattern

The question asks whether any root-to-leaf path succeeds. This is an existential search:

Does at least one candidate path satisfy the condition?

DFS fits naturally. It follows one path downward, checks whether that path can finish successfully, then backs up and tries another branch. As soon as one branch succeeds, the entire search can stop.

Consider this tree:

      5
     / \
    3   8
   /
  2

Suppose targetSum = 8.

The path 5 → 3 reaches a sum of 8, but node 3 is not a leaf. That path is invalid. The complete left path is 5 → 3 → 2, whose sum is 10. The right path is 5 → 8, whose sum is 13.

The answer is False.

This is a path-context DFS problem. Every recursive call needs to know how the values already visited affect the remaining path.

That boundary separates this problem from maximum path sum, where a path may start and end at arbitrary nodes, and from arbitrary node-to-node path queries. Different path boundaries create different state. Here, the root and leaf define the entire algorithm.

Compress the path into one integer

A direct solution could store every node value in a list:

1. Walk from the root toward a leaf.
2. Append each value to a path list.
3. Sum the list at the leaf.
4. Return True if it equals targetSum.

That works conceptually, but the output is only a boolean. We do not need to reconstruct the path.

Instead, carry one integer. There are two equivalent choices:

• current_sum: the sum collected from the root so far
• remaining: the amount still required to reach the target

I prefer remaining because the recursive contract becomes precise:

Starting at this node, can we reach a leaf whose values add up to remaining?

At an internal node, subtract its value before exploring a child. At a leaf, compare the leaf value directly with the remaining target.

The full path disappears. Its relevant history is compressed into one number.

Derive the recursive contract

Define:

dfs(node, remaining)

to mean:

Starting at node, does there exist a path to a leaf whose node values sum to remaining?

Once this contract is clear, the cases follow from the problem statement.

Empty node

An empty child cannot form a root-to-leaf path:

if node is None:
    return False

Do not treat a missing child as a successful zero-length path.

Leaf node

A leaf has no children. This is the only point where the path is allowed to finish.

if node.left is None and node.right is None:
    return node.val == remaining

The leaf check must happen before descending. Otherwise, a matching internal node could incorrectly return True.

Internal node

The current node contributes node.val, so each child must solve the reduced problem:

next_remaining = remaining - node.val

Either child may contain a valid path:

return (
    dfs(node.left, next_remaining)
    or dfs(node.right, next_remaining)
)

The or is not just convenient syntax. It expresses the problem's existential requirement: one successful branch is enough.

The invariant that makes the code correct

The key invariant is:

When dfs(node, remaining) begins, remaining equals targetSum minus the values on the path from the root to the parent of node.

At the root, no values have been consumed, so remaining is the original targetSum.

Each descent subtracts exactly the value of the node being processed. Therefore, when the search reaches a leaf, this test:

node.val == remaining

is equivalent to saying:

sum of the complete root-to-leaf path == targetSum

That is the correctness mechanism. DFS supplies the movement; the invariant gives the state its meaning.

Dry-run the state

Use this tree with targetSum = 22:

        5
       / \
      4   8
     / \   \
    3   6   7
             \
              2

The path 5 → 8 → 7 → 2 sums to 22.

The left branch fails:

Node	Remaining on entry	Result
5	22	Internal; pass 17 to both children
4	17	Internal; pass 13 to both children
3	13	Leaf; 3 != 13, return False
6	13	Leaf; 6 != 13, return False

The right branch succeeds:

Node	Remaining on entry	Result
8	17	Internal; pass 9 to its children
7	9	Internal; pass 2 to its child
2	2	Leaf; 2 == 2, return True

At the root, the logic is equivalent to:

dfs(4, 17) or dfs(8, 17)

Once the right branch returns True, Python's or short-circuits. There is no reason to inspect another branch after finding a valid path.

A one-node tree is also worth checking:

  7

With targetSum = 7, the root is a leaf, so the answer is True. A path containing one node is still a complete root-to-leaf path.

Recursive Python implementation

The recursive version mirrors the derivation directly:

from typing import Optional


class Solution:
    def hasPathSum(
        self,
        root: Optional[TreeNode],
        targetSum: int
    ) -> bool:
        def dfs(node: Optional[TreeNode], remaining: int) -> bool:
            if node is None:
                return False

            if node.left is None and node.right is None:
                return node.val == remaining

            next_remaining = remaining - node.val

            return (
                dfs(node.left, next_remaining)
                or dfs(node.right, next_remaining)
            )

        return dfs(root, targetSum)

Each part answers a specific obligation:

• node is None rejects nonexistent paths.
• The leaf test enforces the required endpoint.
• next_remaining carries path context without copying the path.
• or means either child may provide the solution.
• The initial call starts at the root with the full target untouched.

No visited set is needed. The traversal moves downward through a binary tree, so it does not face the cycle problem found in general graphs.

The Python recursion-depth boundary

The recursive algorithm is correct, but there is an implementation detail you should not ignore.

A legal input can be a highly skewed tree with close to 5,000 nodes:

1
 \
  1
   \
    1
     \
      ...

The recursive call chain then grows with the tree height. In Python, that depth can exceed the runtime's recursion limit even though the algorithm's logic is valid.

So there are two separate questions:

1. Is the recurrence correct? Yes.
2. Is recursion the safest Python implementation for every allowed tree shape? Not necessarily.

For interview explanation, recursion is often the clearest way to derive the invariant. For production-quality handling of the full node bound, an explicit stack removes the dependency on Python's call stack.

Iterative Python implementation

The iterative version preserves exactly the same state contract. Each stack entry stores:

(node, remaining)

That pair means the same thing as dfs(node, remaining).

from typing import Optional


class Solution:
    def hasPathSum(
        self,
        root: Optional[TreeNode],
        targetSum: int
    ) -> bool:
        if root is None:
            return False

        stack = [(root, targetSum)]

        while stack:
            node, remaining = stack.pop()

            if node.left is None and node.right is None:
                if node.val == remaining:
                    return True
                continue

            next_remaining = remaining - node.val

            if node.right is not None:
                stack.append((node.right, next_remaining))

            if node.left is not None:
                stack.append((node.left, next_remaining))

        return False

The order in which the children are pushed is not required for correctness. It only determines which branch the stack explores first.

Notice what did not change:

• Empty trees still return False.
• Only leaves are checked.
• The current node is subtracted before moving downward.
• One successful leaf immediately returns True.
• The stack stores only the state required by the recursive contract.

This is the important translation skill: when recursion is unsafe or inconvenient, do not invent a different algorithm. Move the call state into an explicit data structure.

Complexity and failure cases

Let n be the number of nodes and h be the tree height.

Time complexity

The worst-case time complexity is:

O(n)

In the worst case, every node must be examined. If a valid path is found early, short-circuiting can make a particular run faster, but the worst-case bound remains linear.

Space complexity

The recursive implementation uses:

O(h)

space for the call stack.

The iterative implementation also uses O(h) auxiliary space in the usual depth-first shape analysis. A skewed tree can require O(n) stored states. Neither implementation stores complete root-to-leaf paths, maps, or visited sets.

Edge cases

Case	Correct reasoning
Empty tree	Return False; no root-to-leaf path exists.
One-node tree matching the target	Return True; the root is also a leaf.
One-node tree not matching	Return False.
Negative node values	Continue normally; do not assume sums only increase.
Target of zero	A path may still succeed through positive and negative values.
Internal node matches the target	Continue descending; it is not a valid endpoint.
Missing child	Treat it as no path, not as a zero-length success.
Highly skewed tree	The algorithm remains correct; prefer the explicit stack when Python recursion depth is a concern.

Common wrong turns reveal the mental model that needs repair:

• Returning True when any node matches the remaining target.
  Add the leaf condition. The endpoint is part of the contract.

• Pruning when the running sum exceeds the target.
  Negative values make that unsafe.

• Checking only one child.
  The valid path may be on either side.

• Building full path lists for a boolean result.
  Keep only the compressed state needed for the next decision.

The reusable interview rule

When a tree problem asks whether any root-to-leaf path satisfies a condition:

1. Define what one subtree must answer.
2. Identify the path context the child needs.
3. Carry only that context.
4. Handle empty nodes and leaves separately.
5. Update the state before descending.
6. Check the condition at the exact boundary named by the problem.

For Path Sum, the context is the remaining sum and the boundary is the leaf.

The transferable move is simple but durable: DFS is the movement; the invariant is the solution.