112. Path Sum

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.

Examples

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: True
# Path 5 → 4 → 11 → 2 has sum 5+4+11+2 = 22.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: False
# Paths: 1→2 sum 3, 1→3 sum 4. No path sums to 5.

Example 3:

Input: root = [], targetSum = 0
Output: False
# Empty tree → no root-to-leaf path.

Constraints

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

Clarification Questions

  1. Empty tree: Return False when root is None?
    Assumption: Yes — no path exists.
  2. Leaf: Only paths that end at a leaf (node with no left and no right child) count?
    Assumption: Yes — we do not count partial paths to an internal node.
  3. Root-only: Single node tree; path is just root.val. So targetSum == root.val → True.

Interview Deduction Process (20 minutes)

Step 1: Recursive definition (5 min)
At each node we have a “remaining” sum (targetSum minus the sum of values from root to current node). If the node is a leaf and remaining equals its value, we have a valid path. Otherwise recurse on left and right with updated remaining.

Step 2: Base cases (5 min)
node is None → return False. If node is a leaf (not node.left and not node.right), return remaining == node.val. Else return dfs(left, remaining - node.val) or dfs(right, remaining - node.val).

Step 3: Iterative (optional, 10 min)
BFS or DFS with a stack/queue of (node, remaining). When we pop a leaf, check remaining == node.val; when we push children, push (child, remaining - node.val).

Solution Approach

Recursive DFS: Pass the remaining sum (e.g. targetSum - sum_so_far). Base: None → False. At a leaf, return remaining == node.val. Otherwise return True if either subtree has a path with remaining - node.val.

Iterative (DFS stack or BFS queue): Store (node, remaining). For each node, if it’s a leaf and remaining == node.val return True; else push children with remaining - node.val. No path found after traversal → False.

Key Insights

  1. Root-to-leaf only — We must reach a leaf; an internal node with the right sum does not count.
  2. Pass remaining — Passing “remaining = targetSum - path sum so far” avoids carrying a running sum and comparing at the end.
  3. Short-circuit — As soon as one subtree returns True, we can return True (no need to explore the other).

Python Solution

Recursive DFS

from typing import Optional


# 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


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

        def dfs(node: Optional[TreeNode], remaining: int) -> bool:
            if node is None:
                return False
            remaining -= node.val
            if node.left is None and node.right is None:
                return remaining == 0
            return dfs(node.left, remaining) or dfs(node.right, remaining)

        return dfs(root, targetSum)

Iterative (DFS with stack)

from typing import Optional, List, Tuple


class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False
        stk: List[Tuple[TreeNode, int]] = [(root, targetSum)]
        while stk:
            node, remaining = stk.pop()
            remaining -= node.val
            if node.left is None and node.right is None:
                if remaining == 0:
                    return True
                continue
            if node.right:
                stk.append((node.right, remaining))
            if node.left:
                stk.append((node.left, remaining))
        return False

Algorithm Explanation

Recursive: At each node we subtract node.val from the remaining target. If the node is a leaf, we return whether remaining is 0. Otherwise we recurse on left and right with the new remaining; if either returns True we return True.

Iterative: We maintain a stack of (node, remaining). Pop a node, subtract its value from remaining. If it’s a leaf and remaining is 0, return True. Otherwise push non-null children with the updated remaining. If the stack is exhausted without finding a valid leaf, return False.

Complexity Analysis

  • Time: O(n) in the worst case — we may visit every node (e.g. no path sums to target). Short-circuit can reduce work when a path is found early.
  • Space: O(h) for recursion stack or explicit stack, where h is the height (O(n) for a skewed tree).

Edge Cases

  • root is None → return False (even if targetSum is 0).
  • Single node: path sum = root.val; return targetSum == root.val.
  • targetSum 0 with empty tree → False; with single node 0 → True.
  • Negative values and negative targetSum are allowed.

Common Mistakes

  • Counting internal nodes — A path that sums to targetSum but does not end at a leaf must return False; only root-to-leaf paths count.
  • Wrong base case for None — Recurse only on non-null children; for node is None return False (we’re past a leaf or hit a null child).
  • Comparing before subtracting — Check the leaf condition after subtracting the current node’s value from remaining.