LeetCode #404 Easy

Sum of Left Leaves

Sum every leaf that is a left child.

treedfs

02

Intuition

A node can't know it's a left child — but its parent can. Pass a flag down: when recursing left, mark it. Add the value only when the flagged node turns out to be a leaf.

How to spot this pattern

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.

03

Approach

1

Parent tags the child

dfs(node, isLeft): if node is a leaf and isLeft, contribute its value.

2

Recurse both sides

dfs(left, True) + dfs(right, False). Right leaves contribute nothing but their subtrees may contain left leaves.

3

Leaf test

leaf = no children. A left child with a subtree is NOT a left leaf — the flag alone isn't enough.

04

Solution & live demo

▶1class Solution:
▶2    def sumOfLeftLeaves(self, root):
▶3        def dfs(node, is_left):
▶4            if not node: return 0
▶5            if not node.left and not node.right:
▶6                return node.val if is_left else 0
▶7            return dfs(node.left, True) + dfs(node.right, False)
▶8        return dfs(root, False)

05

Common pitfalls

Adding left children rather than left leaves

✗ Wrong

if node.left:
    total += node.left.val

✓ Right

if not node.left and not node.right:
    return node.val if is_left else 0

The 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

✗ Wrong

if node.left and not node.left.left and not node.left.right:
    total += node.left.val

✓ Right

def dfs(node, is_left):
    if not node.left and not node.right:
        return node.val if is_left else 0

It 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

✗ Wrong

return dfs(root, True)

✓ Right

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.

06

Edge cases

Root only

Root is nobody's child → 0.

Left child with its own children

Not a leaf — recursion continues inside it instead of adding.

07

Complexity

Time

O(n)

Space

O(h)

Plain DFS with a boolean.