112 · Path Sum

The leaf test, isolated. root == null returning false is correct; root.left == null && root.right == null is the actual leaf condition. Most people conflate them once, and then forever — this problem exists to make that happen here, cheaply, instead of in an interview.

1 — The problem

Does some root-to-leaf path sum to targetSum? The natural formulation carries the remaining target downward — sub-variant D's machinery — and tests it at leaves, which is what makes this the entry point to sub-variant E.

Two guards are needed and they answer different questions:

Guard	Question	Returns
`nd == null`	Is there a node here at all?	false — an absent branch offers no path. It is not a place where a path ends.
`nd.left == null && nd.right == null`	Does a path end here?	`nd.val == rem` — the only place the target may be checked.

Collapsing these into one is the classic error, and it has a specific, seductive shape: if (nd == null) return rem == 0;. It looks tidy, it passes the sample, and it is wrong.

2 — Subtracting on the way down

Target 22. Watch rem shrink along each path and get tested exactly once, at the leaf. Node 7 arrives with 2 remaining and fails; its sibling 2 arrives with the same 2 and succeeds.

Node 8 and its whole subtree are never entered. The || on line 5 got true from the left and stopped — the same short-circuit that made LC 572 tolerable and LC 110 linear.

2.1 The single-child counterexample

Here is the smallest tree that separates the two base-case styles — [1,2] with target 1:

Base case	What happens	Answer
Leaf test — `nd.left == null && nd.right == null`	Node 1 is not a leaf (it has a left child), so no test fires there. Node 2 is a leaf and is tested against `1 - 1 = 0`; `2 != 0`.	false — correct
`nd == null` → `rem == 0`	Node 1's right child is null and arrives with `rem = 0`, because 1 was already subtracted.	true — wrong. It claims a path ending at a node that does not exist.

The tree in the visualizer would not catch this: every node there has either two children or none. That is exactly why the bug survives casual testing — the LeetCode samples for this problem are all well-branched, and the single-child case has to be constructed deliberately.

2.2 The other direction: accumulate instead of subtract

Carrying sum + nd.val downward and comparing to target at the leaf is equally valid, and identical in structure:

Java 21Accumulating variant — same shape, same leaf test.6 lines

boolean go(TreeNode nd, int sum, int target) {
    if (nd == null) return false;
    sum += nd.val;
    if (nd.left == null && nd.right == null) return sum == target;
    return go(nd.left, sum, target) || go(nd.right, sum, target);
}

Subtracting is marginally nicer because it carries one parameter instead of two. Neither version rescues you from the leaf test — the trap is in where you compare, not in what you compare.

3 — Complexity and edge cases

Time O(n) worst case, less with the short-circuit. Space O(h).
Empty tree: false for any target, including 0. There are no root-to-leaf paths in an empty tree, so nothing can sum to anything — the nd == null guard gets this right and return rem == 0 gets it wrong.
Single node: true iff its value equals the target. It is a leaf.
Negative values: fully supported, and they break every "prune when rem < 0" optimisation. Do not add one unless the constraints promise positive values.
Common bug: the null-based base case, as above.
Common bug: testing rem == 0 at the leaf instead of nd.val == rem — that forgets to spend the leaf's own value. It is right only if you subtract before the test.

4 — Reference implementation

Java 21Subtracting variant, matching the visualizer.6 lines

public boolean hasPathSum(TreeNode nd, int rem) {
    if (nd == null) return false;                    // no node, no path
    if (nd.left == null && nd.right == null)          // a path ends here
        return nd.val == rem;
    return hasPathSum(nd.left,  rem - nd.val)
        || hasPathSum(nd.right, rem - nd.val);
}

Next: LC 257 keeps this leaf test and adds a mutable path; LC 113 is the two of them composed.