LeetCode 112 – Path Sum

Path Sum looks like a three-line recursion and contains a base case that almost everyone writes wrong. The mistake is subtle enough to pass the LeetCode examples and fail on a four-node tree, and it comes from the same confusion as Minimum Depth: null is not the same thing as a leaf.

The problem

Given a binary tree and a target sum, return whether the tree has a root-to-leaf path whose values add up to the target.

      5
     / \
    4   8        target 22 -> true    5 + 4 + 11 + 2
   /   / \
  11  13  4
 /  \      \
7    2      1

  [1,2,3]  target 5  -> false   paths are 1+2=3 and 1+3=4
  []       target 0  -> false   no path at all, not even an empty one
  [1,2]    target 1  -> false   1 is not a leaf
  [-2,null,-3] target -5 -> true

[1,2] with target 1 is the case to have ready. Node 1 has a child, so the path cannot stop there — and the naive base case says it can.

The base case everyone gets wrong

The instinct is to subtract as you descend and, at a null, report whether the remainder reached zero:

if (root == null) return targetSum == 0;      WRONG

Walk [1,2] with target 1 through it. At the root the remainder becomes 0, then the recursion enters the null right child, sees targetSum == 0 and returns true. It has just accepted a path that stops at node 1, which is not a leaf.

The correct base cases separate the two ideas:

root == null                       -> false     an absent node is not a path
root is a leaf (no children)       -> targetSum == root.val
otherwise                          -> recurse with targetSum - root.val

The leaf test belongs on the node, not on its absent children. Say that out loud — it is the distinction the problem exists to check, and it recurs in every root-to-leaf problem.

Java

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;      // NOT "targetSum == 0" -- null is not a leaf

        if (root.left == null && root.right == null) {
            return targetSum == root.val;    // a real leaf: this is the last node
        }

        int remaining = targetSum - root.val;
        return hasPathSum(root.left, remaining)
            || hasPathSum(root.right, remaining);
    }
}

Recursing into a null child from a one-child node is harmless: it returns false and the || lets the real side decide. That is why no guard is needed around the recursive calls.

|| short-circuits, so a match in the left subtree means the right is never walked. Free early exit, from writing the natural thing.

Python

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

        if root.left is None and root.right is None:
            return targetSum == root.val

        remaining = targetSum - root.val
        return (self.hasPathSum(root.left, remaining)
                or self.hasPathSum(root.right, remaining))

Negative values kill the obvious optimisation

A tempting pruning rule is to give up on a branch once the running sum exceeds the target. It is wrong the moment values can be negative, and LeetCode's constraints allow them:

      10
        \
        -8         target 2:  after 10 the running sum already exceeds it,
          \                   but -8 then +... brings it back
           0

With only non-negative values the pruning is valid and worth mentioning as a conditional optimisation. Stating the precondition rather than the rule is what makes it a good answer instead of a bug.

The iterative version

Carry the remaining target alongside each node on the stack:

    boolean hasPathSumIterative(TreeNode root, int targetSum) {
        if (root == null) return false;

        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> remaining = new ArrayDeque<>();
        nodes.push(root);
        remaining.push(targetSum - root.val);

        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int left = remaining.pop();

            if (node.left == null && node.right == null && left == 0) return true;

            if (node.right != null) {
                nodes.push(node.right);
                remaining.push(left - node.right.val);
            }
            if (node.left != null) {
                nodes.push(node.left);
                remaining.push(left - node.left.val);
            }
        }

        return false;
    }

Two parallel stacks kept in lockstep. A single stack of pairs is cleaner if you have a pair type to hand; the point either way is that the recursion's implicit state — how much target is left — becomes something you carry explicitly.

Complexity

Worst case every node is visited; the short-circuit helps whenever a match exists. No sub-linear approach is possible — the matching path could be anywhere.

The pattern

Path Sum II (113) returns all such paths, which turns it into backtracking: carry the path, append and pop around the recursive calls, and copy it when recording — the same defensive copy as Subsets. Path Sum III (437) drops the root-to-leaf requirement and becomes a prefix-sum problem, which is a genuinely different technique despite the name.

Subtracting as you descend, rather than accumulating and comparing at the end, is the small habit worth taking away: it keeps the recursion's signature the same at every level.

What the interviewer is checking

• That root == null returns false rather than testing the remainder.
• That the leaf test is no children, checked on the node itself.
• [1,2] with target 1 returning false.
• The empty tree returning false even for target 0.
• That negative values rule out sum-based pruning, and that you say so.
• That || gives an early exit for free.
• Whether you can extend it to Path Sum II without restructuring.