Path Sum (LC 112)

Pattern: DFS (Top-Down with accumulator / subtraction)
Difficulty: Easy
Key Concept: Decrement a running “remaining sum” along each root-to-leaf path; at a leaf, remaining must be exactly zero.

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 the sum of node values on that path equals targetSum.

A leaf is a node with no left and no right child.

Input: TreeNode root, int targetSum.
Output: boolean — whether at least one valid root-to-leaf path sums to targetSum.

Edge: If root == null, return false (empty tree has no path).

Example tree (LeetCode array
[5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22):

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

Path 5 → 4 → 11 → 2 sums to 5 + 4 + 11 + 2 = 22 → true.

---

1. Algorithm & Pseudocode

Brute force (collect all root-to-leaf sums)

collectPaths(node, currentPath, allSums):
  if node is null: return
  append node.val to currentPath
  if node is leaf:
    allSums.add(sum(currentPath))
  else:
    collectPaths(node.left, currentPath, allSums)
    collectPaths(node.right, currentPath, allSums)
  remove last from currentPath   // backtrack

hasPathSum(root, targetSum):
  if root is null: return false
  sums = empty list
  collectPaths(root, empty list, sums)
  return sums contains targetSum

Idea: Enumerate every root-to-leaf path, compute each path sum, check for targetSum.

Optimal (DFS, subtract along the way)

hasPathSum(node, remaining):
  if node is null: return false
  remaining = remaining - node.val
  if node is leaf (left null and right null):
    return remaining == 0
  return hasPathSum(node.left, remaining) OR hasPathSum(node.right, remaining)

Idea: No list of all paths; carry only the remaining value needed after visiting the current node.

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why only root-to-leaf?
   The problem asks for a path from root to a leaf. Stopping at an internal node with sum targetSum does not count.

2. Why subtract targetSum?
   Equivalently you can add node values and compare to targetSum at the leaf. Subtracting turns the question into “did we exactly use up the budget at a leaf?” which reads cleanly at the base case.

3. Leaf definition:
   node.left == null && node.right == null. If one child is missing, that node is not a leaf (unless both are null in a single-node tree).

4. Bug: node == null && remaining == 0:
   After recursing past a leaf’s missing child, you hit null with remaining possibly 0. Returning true there would wrongly accept paths that end above a leaf. The safe pattern is: return false for null, and only return true at a leaf when remaining == 0.

5. Empty tree:
   root == null → no path → false.

---

3. The Dry Run

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

Optimal DFS: dfs(node, remaining) subtracts node.val inside the call (or before recursing). Below, “remaining (enter)” is the value before subtracting the current node’s value; “remaining (after)” is after subtracting that node.

Trace along the winning path 5 → 4 → 11 → 2

Step	node.val	remaining (enter)	remaining (after)	Is leaf?	Branch result
1	5	22	17	no	need children
2	4	17	13	no
3	11	13	2	no
4	2	2	0	yes	0 == 0 → true

Once the leaf 2 returns true, the OR chain propagates true up; answer is true.

Trace along a failing leaf 5 → 4 → 11 → 7

Step	node.val	remaining (enter)	remaining (after)	Is leaf?	Branch result
1	5	22	17	no
2	4	17	13	no
3	11	13	2	no
4	7	2	-5	yes	-5 == 0 → false

So from node 11, left returns false, right returns true, and false || true is true.

Trace along path 5 → 8 → 4 → 1 (all nodes to leaf 1)

Step	node.val	remaining (enter)	remaining (after)	Is leaf?	Branch result
1	5	22	17	no
2	8	17	9	no
3	4	9	5	no
4	1	5	4	yes	4 == 0 → false

---

4. Java Solution

Brute Force

Idea: Collect every root-to-leaf sum in a list, then check containment.

Time: O(n) — visit each node once.
Space: O(n) — path list + recursion + storing sums.

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

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        List<Integer> sums = new ArrayList<>();
        collect(root, new ArrayList<>(), sums);
        return sums.contains(targetSum);
    }

    private void collect(TreeNode node, List<Integer> path, List<Integer> sums) {
        if (node == null) {
            return;
        }
        path.add(node.val);
        if (node.left == null && node.right == null) {
            int sum = 0;
            for (int v : path) {
                sum += v;
            }
            sums.add(sum);
        } else {
            collect(node.left, path, sums);
            collect(node.right, path, sums);
        }
        path.remove(path.size() - 1);
    }
}

Optimal

Time: O(n) worst case. Space: O(h) stack.

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return dfs(root, targetSum);
    }

    private boolean dfs(TreeNode node, int remaining) {
        if (node == null) {
            return false;
        }
        remaining -= node.val;
        if (node.left == null && node.right == null) {
            return remaining == 0;
        }
        return dfs(node.left, remaining) || dfs(node.right, remaining);
    }
}

---

5. The “Java vs. Others” Edge

• Leaf check: Always use node.left == null && node.right == null. A node with one null child is not a leaf; do not treat reaching null with remaining == 0 as success.
• Same bug in C++: Pointer to nullptr with remaining 0 is a classic false positive if you mishandle the base case.
• Empty tree: root == null → return false immediately; there is no root-to-leaf path.
• Integer overflow: For very large sums, remaining could overflow int in theory; interview trees usually stay within safe ranges. For production, consider long for accumulated sums.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Every node visited; path list + list of sums
Optimal	O(n)	O(h)	O(1) extra per stack frame; h = height

n = number of nodes. Worst case skewed tree: h = n.