404 · Sum of Left Leaves

An aggregate whose predicate depends on the edge you arrived by, not on the node. A leaf cannot tell whether it is a left leaf — that fact belongs to its parent, so it has to be handed down.

○ optional rep for sub-variant A

1 — The problem

Sum the values of every leaf that is a left child. Two conditions, and they live in different places:

Condition	Known by	Carried how
Is it a leaf?	the node itself	`nd.left == null && nd.right == null` — a local test
*Is it a left* child?**	its parent	a `boolean` parameter, set at the call site

That second row is the whole content of the problem. A node has no pointer to its parent and no idea which side of it it hangs from, so the information cannot be recovered downward — it has to be pushed. Sub-variant D's machinery, applied to a sub-variant A aggregate.

2 — A flag set at the call site

Watch the arrived by strip. It is not a property of the node being visited; it is set by whichever of the two calls on lines 4–5 made the visit happen.

Node 20 arrives with isLeft = false and is ignored — but not because of the flag. It is ignored because it is not a leaf, and the flag never gets consulted. Only line 4 reads it, and only leaves reach line 4.

2.1 The two ways to get it wrong

Mistake	What it computes instead
Adding `nd.left.val` whenever the left child exists	The sum of all left children, leaf or not. Wrong on any tree where a left child has children of its own — which the sample tree does not, so it passes.
Checking `isLeft` before the leaf test	Every left node, at every depth. Same failure, reached from the other direction.

Both come from collapsing two independent conditions into one check. Keep them separate: the leaf test gates whether to contribute, the flag decides how much.

2.2 The parent-side variant

The flag can be avoided by having the parent inspect its own left child — some people find this clearer, and it makes the "leaf, not merely a child" requirement visible in one place:

Java 21Parent-side test — no extra parameter.8 lines

public int sumOfLeftLeaves(TreeNode nd) {
    if (nd == null) return 0;
    int total = 0;
    if (nd.left != null && nd.left.left == null && nd.left.right == null)
        total += nd.left.val;                    // a left child that is also a leaf
    else total += sumOfLeftLeaves(nd.left);      // else recurse into it
    return total + sumOfLeftLeaves(nd.right);
}

Note the else: without it, a left leaf would be counted and then recursed into — harmless here, since a leaf's children are null, but it signals the author has not decided which case is which. The parameter version has no such ambiguity, which is why it is the one worth internalising.

3 — Complexity and edge cases

Time O(n), space O(h).
Empty tree: 0.
Single node: 0 — the root is a leaf, but it is nobody's left child. The top-level call must pass false.
A left-only chain: only the final node counts, not every node on it. The leaf test is doing the work.
A right child that is a leaf: contributes nothing — the case that distinguishes this from "sum of all leaves".
Common bug: seeding the root call with true. Wrong on a single-node tree and nowhere else, so it survives most testing.

4 — Reference implementation

Java 21Flag carried down, matching the visualizer.8 lines

public int sumOfLeftLeaves(TreeNode root) {
    return sum(root, false);          // the root is nobody's left child
}

private int sum(TreeNode nd, boolean isLeft) {
    if (nd == null) return 0;
    if (nd.left == null && nd.right == null)
        return isLeft ? nd.val : 0;    // leaf: the flag decides
    return sum(nd.left, true) + sum(nd.right, false);
}