Path Sum — LeetCode 112 Root-to-Leaf DFS for FAANG Interviews

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.

Constraints:

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

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

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

Why This Problem Matters#

LeetCode 112 — Path Sum introduces the most-tested tree pattern in FAANG interviews: DFS with a running accumulator that resets implicitly via recursion. Amazon, Microsoft, Apple, and Meta use it as the natural step-up after Maximum Depth, because it adds two new wrinkles — a target argument and the leaf check.

Interviewers love it because the leaf condition trips most candidates. A node with one null child is not a leaf — only nodes where both children are null qualify. Engineers who code if not root: return root.val == target get wrong answers on [1, 2].

It is also the gateway problem to Path Sum II (collect all paths), Path Sum III (count subpaths anywhere), Sum Root to Leaf Numbers, and Maximum Path Sum. Master this one and the entire path-sum family unlocks.

The Core Insight#

Subtract instead of accumulate. At each node, pass target - root.val down to the children. When you hit a leaf, check whether the remaining target equals the leaf's own value (which means the path sum hit zero exactly when we consume the leaf).

The base case for a null node is False — an empty path sums to 0, never to the target. The leaf check is if not node.left and not node.right: return node.val == target.

This subtractive form is cleaner than an additive accumulator because it removes a parameter and works naturally with recursion.

Visual Dry Run#

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

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

A path 5 -> 4 -> 11 -> 2 sums to 22, so the answer is true.

Solution (Optimal)#

# Python — recursive DFS with subtractive target
class Solution:
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        # Leaf check — only return true at a real leaf
        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))

// JavaScript — same recursion
var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) return root.val === targetSum;
    const rem = targetSum - root.val;
    return hasPathSum(root.left, rem) || hasPathSum(root.right, rem);
};

# Iterative DFS — pair (node, remaining) on a stack
class Solution:
    def hasPathSum(self, root, targetSum):
        if not root: return False
        stack = [(root, targetSum)]
        while stack:
            n, t = stack.pop()
            if not n.left and not n.right and n.val == t:
                return True
            if n.right: stack.append((n.right, t - n.val))
            if n.left:  stack.append((n.left,  t - n.val))
        return False

Time: O(n) — every node is visited once in the worst case. Space: O(h) recursion depth, where h is the tree height.

Common Mistakes#

• Treating a node with one null child as a leaf — only not left and not right is a leaf.
• Returning True at a null when the remaining target hits 0 — that wrongly accepts paths that end mid-tree.
• Accumulating sum top-down with a default value that is mutated across recursive calls.
• Counting an empty tree as having any path sum — return False for root is None.

Interview Tips#

• Clarify whether "path" means root-to-leaf or any-to-any (LC 112 is the former, LC 437 the latter).
• Verify negative values are allowed — they are, which means greedy pruning by remaining-positive does not work.
• Sketch a tree where one child is null and demonstrate the leaf check.
• Mention Path Sum II/III as the natural follow-ups.

Follow-up Questions#

• Return all paths summing to target (LC 113)? Carry a path list and append a copy at each leaf hit.
• Count any-direction paths (LC 437)? Prefix-sum hash map on the tree.
• Return only the path with maximum sum? Tree-DP with max-path-from-leaf.
• Allow non-leaf endings? Drop the leaf check; check at every node.
• What if target is huge (10^18)? Use Python ints or 64-bit; the algorithm is unchanged.

Key Takeaways#

• LeetCode 112 Path Sum runs in O(n) time and O(h) space with recursive DFS.
• The pattern is subtractive: pass target - root.val down to children.
• A leaf is a node with both children null — single-child nodes are not leaves.
• Asked at Amazon, Microsoft, Apple, Meta, Bloomberg as a path-DFS warmup.
• Foundation for Path Sum II (LC 113), Path Sum III (LC 437), Sum Root to Leaf Numbers (LC 129).
• Iterative version uses a stack of (node, remaining) pairs.
• Negative node values are allowed — do not prune when target < 0.