129 · Sum Root to Leaf Numbers

Sub-variant D with a transformed accumulator: the value flowing down is rebuilt at every level as cur * 10 + val, and it is harvested only at leaves. Watch what "leaf" means here — it is not "null", and conflating the two is the bug this problem is built to expose.

1 — The problem

Each root-to-leaf path spells a number, digit by digit. Sum them all. The tree [4,9,0,5,1] spells 495, 491 and 40, totalling 1026.

Two things flow, in opposite directions:

The accumulator differs from LC 1448's in one important way: it is not idempotent. Applying max twice with the same value changes nothing, so a sloppy 1448 still works. Applying * 10 + twice appends a digit that is not there. Order and count both matter, which makes this the better test of whether you actually understand where the transformation happens.

2 — Building the number on the way down

Follow cur: 4, then 49, then 495 — harvested. Then the recursion unwinds to 49 and descends again into 1, giving 491. The digit 9 is never removed by hand; it disappears because the stack frame that held it returned.

Node 0 is a leaf, so it harvests 40 — a two-digit number from a two-node path, with a leading digit of 4 and a trailing 0. Nothing special is needed for the zero; the arithmetic handles it.

2.1 The leaf test, and why null is not it

There are two plausible places to harvest, and only one is right:

The doubling is the friendly failure. The nastier one is the single-child node: on a tree like [1,2] the null-harvesting version also collects the incomplete path through node 1's missing right child, adding a 1 that no leaf ever spelled.

Compare with LC 104, where basing everything on null is exactly right. The distinction: 104 aggregates over nodes, and null is the identity for that. This problem aggregates over paths, and a path ends at a leaf. Sub-variant E exists to keep those apart — see LC 112, where the same trap has teeth.

2.2 Why no backtracking is needed

The obvious worry: after finishing the left subtree, does cur need to be "un-extended" before going right? No — and the reason is worth internalising, because it is what separates sub-variant D from sub-variant E.

• cur is an int, passed by value. The line cur = cur * 10 + nd.val rebinds a local, and the caller's copy is untouched. Each frame gets its own.
• In LC 257 the accumulator is a List, passed by reference, and all frames share one object. That is when you must remove after recursing.

The rule: immutable state flowing down needs no backtracking; mutable shared state does.

3 — Complexity and edge cases

• Time O(n), space O(h). Each node contributes one multiply-add.
• Single node: its value. It is a leaf, so line 5 fires immediately.
• A node with exactly one child is not a leaf and must not harvest. This is the case that separates the two base-case styles.
• Zeros: [0,1] spells 01 = 1. No leading-zero handling is required — the arithmetic produces it.
• Overflow: LeetCode caps depth at 10, so the largest number is 10 digits and int is enough — barely. Deepen the tree and this is the first thing to break; long costs nothing.
• Common bug: writing return cur + sum(left, cur) + sum(right, cur) — adding the running value at every node instead of only at leaves. Internal nodes are not complete numbers.

4 — Reference implementation

public int sumNumbers(TreeNode root) {
    return sum(root, 0);
}

private int sum(TreeNode nd, int cur) {
    if (nd == null) return 0;            // absent branch adds nothing
    cur = cur * 10 + nd.val;                 // extend on the way down
    if (nd.left == null && nd.right == null) return cur;   // harvest at leaves only
    return sum(nd.left, cur) + sum(nd.right, cur);
}

Both base cases are present and they do different jobs: line 6 handles a missing branch, line 8 handles a completed path. Most wrong solutions have only one of them.