Sum of Left Leaves
Sum of Left Leaves: sum every leaf that is a left child.
- The number of nodes in the tree is in the range [1, 1000].
- -1000 <= Node.val <= 1000
Intuition
The sum of left leaves problem asks you to add up every leaf that happens to be a left child. Two conditions must hold at once, and the difficulty is that they are known in different places. Whether a node is a leaf is something the node can determine itself: it has no children. But whether it is a left child is not visible from the node at all — a node has no idea which side of its parent it hangs from. Only the parent knows that. So the information has to travel downward. When recursing into a left child, pass a flag saying so; when recursing right, pass the opposite. Each call then has both facts available and can decide whether to contribute: - Add the value only when the node is a leaf and the flag says it is a left child. Both conditions are necessary. A left child that has children of its own is not a left leaf — it is an internal node, and it contributes nothing itself even though its subtree may contain left leaves further down. Likewise, a leaf reached as a right child contributes nothing, though its parent's other branch might. The recursion therefore always explores both sides regardless of the flag. It is only the contribution that is filtered, never the traversal.
When a node's contribution depends on how you arrived, pass that context down as a parameter. The node itself cannot tell whether it's a left or right child, so the parent supplies the answer at the call site. That trick — pushing context into the recursion — is what makes this a two-line change rather than a parent-pointer problem.
Approach
Before reading on: price up what the direct approach costs here, then ask what each node needs from its children before it can answer. Aim for O(n) time and O(h) space.
Pass the side information down
Define dfs(node, isLeft) where the boolean is supplied by the parent. A node cannot determine which side it is on, so this flag is the only way that fact reaches the place where the decision is made.
Return zero for a null node
If the node is null, contribute 0. Handling this at the top of the function means the caller does not have to check whether each child exists before recursing, keeping the recursive calls uniform.
Contribute only when both conditions hold
If the node has no children and isLeft is true, return its value — this is a left leaf. If it is a leaf but a right child, return 0. Both tests together are what define the target, and dropping either one produces a wrong sum.
Always recurse into both subtrees
Return dfs(node.left, true) + dfs(node.right, false). The right subtree is explored even though right children never contribute directly, because a left leaf can live anywhere inside it. Skipping it is a common and quietly incorrect optimisation.
Cost of the traversal
Every node is visited exactly once and does O(1) work, giving O(n) time. Space is O(h) for the recursion stack, which is O(log n) on a balanced tree and O(n) on a fully skewed one.
Solution & live demo
Common pitfalls
Adding left children rather than left leaves
if node.left:
total += node.left.valif not node.left and not node.right:
return node.val if is_left else 0The question asks for leaves that happen to be left children, not every left child. An internal left node contributes nothing itself — only its leaf descendants do.
Checking leaf-ness from the parent
if node.left and not node.left.left and not node.left.right:
total += node.left.valdef dfs(node, is_left):
if not node.left and not node.right:
return node.val if is_left else 0It works, but it reaches two levels down and duplicates the leaf test for each side. Passing a flag lets each node answer for itself, which is far easier to extend to deeper questions.
Seeding the root as a left child
return dfs(root, True)
return dfs(root, False)
The root has no parent, so it's neither a left nor a right child. A single-node tree would otherwise report its value, when the correct answer is 0.
Edge cases
Root is nobody's child → 0.
Not a leaf — recursion continues inside it instead of adding.