A coupon engine stores each fee as a binary tree: the plan is the root, add-ons fork left and right, and only a SKU leaf is what actually charges. Support asked whether any root-to-leaf chain sums to the customer’s coupon. The intern returned true as soon as a mid-tier add-on’s fee equaled the coupon, even though that node still had children — the coupon never landed on a real SKU.

A path counts only when remaining hits zero at a leaf. Recurse with target - node.val. Do not stop because an internal node equals the original target. Empty is false: there is no leaf.

The problem

Given the root of a binary tree and an integer target, return whether any root-to-leaf path sums to that target. A leaf has no children. An empty tree is false. A single node is true only when its value equals the target.

final class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

Sample trees. The first drawing is the trap: the root’s value equals the target, and it is not a leaf.

      5
     / \
    4   8     target 5  →  false
              5 matches the root; paths are 9 and 13

      5
     / \
    4   8     target 9  →  true   (5 + 4)

    1
   /
  2               target 1  →  false
                  1 matches the root; the only leaf path is 3

[]            target 0  →  false
[1]           target 1  →  true
[1]           target 0  →  false

Note: A node with one child is not a leaf. Do not treat null as a successful remaining of 0 — that makes the empty tree true for target 0, and it lets a missing child “finish” a path that never reached a leaf.

Collect every root-to-leaf sum is the honest brute force

From the root, add node.val as you walk, record the sum at each leaf, then ask whether the list contains the target. Correct. Extra: you materialize every leaf sum you never needed once a match exists, and you think in “paths stored” instead of “remaining at this node.”

boolean hasPathSumCollect(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    List<Integer> leafSums = new ArrayList<>();
    collect(root, 0, leafSums);
    return leafSums.contains(targetSum);
}

void collect(TreeNode node, int acc, List<Integer> leafSums) {
    int sum = acc + node.val;
    if (node.left == null && node.right == null) {
        leafSums.add(sum);
        return;
    }
    if (node.left != null) {
        collect(node.left, sum, leafSums);
    }
    if (node.right != null) {
        collect(node.right, sum, leafSums);
    }
}

At a dozen nodes this is a rounding error. At a million-node spine you still visit everyone, plus a list of leaf sums. The intended answer never stores that list: true only when a leaf’s remaining is 0.

Remaining, then a leaf

Null returns false — no leaf. A leaf returns node.val == remaining (equivalently, remaining after subtracting the leaf is 0). Any other node subtracts node.val and is true if either child is. The drawing with target 5 never returns true at the root: remaining becomes 0 there, but the root has children, so both sides keep going with remaining 0 against 4 and 8.

hasPathSum(5, 5) → remaining 0, not a leaf
hasPathSum(4, 0) → leaf, 4 == 0? false
hasPathSum(8, 0) → leaf, 8 == 0? false     →  false

hasPathSum(5, 9) → remaining 4, not a leaf
hasPathSum(4, 4) → leaf, 4 == 4            →  true

hasPathSum(1, 1) → remaining 0, not a leaf
hasPathSum(2, 0) → leaf, 2 == 0? false
hasPathSum(null, 0) → false                →  false

The Java is that recurrence:

boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }
    int remaining = targetSum - root.val;
    return hasPathSum(root.left, remaining) || hasPathSum(root.right, remaining);
}

Time is O(n) — each node is visited once, and you can stop early on the first true. Space is O(h) for the call stack, h being height. A spine of a million nodes is a million frames; an ArrayDeque of (node, remaining) is the same bound without blowing the JVM stack.

What interviewers usually poke next

  • Internal match. If they draw a root whose value equals the target and then ask why you did not return true, name the leaf rule before you touch the code.
  • Negatives. Node values can be negative. Remaining can go below zero and recover. Do not prune remaining < 0 unless they promise all values are positive.
  • Path Sum II. Return every root-to-leaf path that hits the target, not a boolean. Same remaining walk; keep the path.
  • Path Sum III. Any downward path, not necessarily root-to-leaf. Do not count prefix paths here.
  • Million-node spine. Recursion depth is O(h). Say you would switch to an ArrayDeque of remaining so the JVM does not blow the stack.

You are done with this problem when you can say empty is false, an internal node whose value equals the target is not a path, and remaining hits zero only at a leaf.