112 - Path Sum

Difficulty: Easy | Pattern: Tree DFS | Company tags: Amazon, Google, Microsoft

Problem Statement

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

        5
       / \
      4   8
     /   / \
    11  13   4
   /  \       \
  7    2        1

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: Path 5→4→11→2 sums to 22.

Example 2:

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

Algorithm Flow

Approach: Recursive DFS

Key insight: At each node, reduce the target by the node's value and recurse. At a leaf node, check if the remaining target equals the leaf's value (i.e., target reduced to 0 after accounting for the leaf).

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

def hasPathSum(root, targetSum: int) -> bool:
    if not root:
        return False
    
    # At a leaf node, check if this completes the target
    if not root.left and not root.right:
        return targetSum == root.val
    
    remaining = targetSum - root.val
    return hasPathSum(root.left, remaining) or hasPathSum(root.right, remaining)

Approach: Iterative DFS (Stack)

Store (node, remaining_sum) pairs on the stack:

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

Dry Run

Tree: 5→4→11→7 and 5→4→11→2 and 5→8→... targetSum = 22

• Start at 5, remaining = 22-5 = 17
• Go left to 4, remaining = 17-4 = 13
• Go left to 11, remaining = 13-11 = 2
• Go left to 7: leaf, 2 ≠ 7 → False
• Go right to 2: leaf, 2 == 2 → True ✓

Edge Cases

• Empty tree → False
• Single node: is it a leaf AND targetSum == node.val?
• targetSum = 0, root = None → False
• Negative node values are allowed; the algorithm handles them correctly

Complexity

• Time: O(n) — visit each node at most once
• Space: O(h) where h is tree height; O(n) worst case (skewed tree)

Key Terms

Term	Definition
Root-to-leaf path	A sequence of nodes from the root down to a leaf, following parent-child links.
Leaf node	A node with no left and no right child.
DFS (Depth-First Search)	Traversal strategy that explores as far as possible along each branch before backtracking.
Remaining sum	The target minus the accumulated sum so far; passed down through recursion instead of tracking a running total.
Recursion tree	The implicit tree of function calls created by recursive DFS, mirroring the shape of the binary tree.

FAQ

1. Can this be solved without extra space? Yes for the recursive version beyond the O(h) call stack — no auxiliary data structure is needed since the remaining sum is passed by value.
2. What if a leaf value equals targetSum but there's another non-leaf node with value 0 along the way? It doesn't matter — the check only happens at leaves, so intermediate zero values are handled naturally by continued subtraction.
3. What if the tree contains negative values? The algorithm still works correctly because it doesn't rely on sums being monotonically increasing; it simply checks equality at each leaf.
4. How is this different from 113 - Path Sum II? 112 only needs a boolean answer (does any valid path exist), so it can short-circuit with early return; 113 must explore all root-to-leaf paths and collect every one that matches.
5. Why check not root.left and not root.right instead of root.val == targetSum alone? Because a non-leaf node could coincidentally match the remaining sum without completing a full root-to-leaf path — the leaf check enforces path completeness.

Quick Revision

• Problem: does any root-to-leaf path sum to targetSum?
• Approach: DFS, subtracting node.val from targetSum as you descend.
• At a leaf, check if the remaining target equals 0 (or equivalently, equals the leaf's value before subtraction).
• Short-circuit with or — return True as soon as one valid path is found.
• Iterative version uses an explicit stack storing (node, remaining) pairs.
• No path exists if root is None — return False immediately.
• Time: O(n); Space: O(h), where h is tree height.
• Negative values don't break the algorithm — only equality at leaves matters.

Related Problems

• 113 - Path Sum II — return all root-to-leaf paths that sum to target, not just a boolean.
• Pattern: Tree DFS with path accumulation, also seen in "Sum Root to Leaf Numbers" and "Binary Tree Maximum Path Sum".