404. Sum of Left Leaves

Reformulated question¶

Given a binary tree, return the sum of values of all leaves that are the left child of their parent.

Example:

input tree:  [3,9,20,null,null,15,7]
left leaves: 9, 15
output:      24

Key trick¶

Carry whether a node is a left child while traversing the tree.

If a node is both: - a left child - a leaf

then add its value.

Trap¶

Counting every left child, even when it is not a leaf.
Counting leaf values without remembering whether they came from a left edge.
Forgetting the root is never a left leaf.

Why is this question interesting?¶

It is a small tree traversal problem where the real point is state propagation, not traversal itself.

It checks whether you can express a node property that depends on its parent.

Solve the problem with idiomatic python¶

class Solution:
    def sumOfLeftLeaves(self, root):
        # DFS with a flag telling whether the node is a left child.
        def dfs(node, is_left):
            if not node:
                return 0

            # Leaf: count it only if it is a left child.
            if not node.left and not node.right:
                return node.val if is_left else 0

            return dfs(node.left, True) + dfs(node.right, False)

        return dfs(root, False)

An iterative version is also a good interview answer:

class Solution:
    def sumOfLeftLeaves(self, root):
        if not root:
            return 0

        total = 0
        stack = [(root, False)]

        while stack:
            node, is_left = stack.pop()

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

            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, True))

        return total

Pytest test¶

import pytest
from utils import tree_build


@pytest.mark.parametrize(
    ("values", "expected"),
    [
        ([3, 9, 20, None, None, 15, 7], 24),
        ([1], 0),
        ([1, 2], 2),
        ([1, None, 2], 0),
        ([1, 2, 3, 4, 5], 4),
        ([1, 2, 3, None, None, 6, 7], 6),
        ([0, -1, 2, -3, None, None, 4], -3),
    ],
)
def test_sum_of_left_leaves(values, expected):
    root = tree_build(values)
    assert Solution().sumOfLeftLeaves(root) == expected

Comment my solution¶

Your solution works, but it is harder to explain than necessary.

Main issues: - left as a separate pointer makes the traversal state unusual. - The logic mixes traversal order and "is this a left leaf?" detection. - In interview code, passing an is_left flag is simpler, shorter, and easier to verify.

A cleaner equivalent idea is:

stack = [(root, False)]

Then for each child: - left child gets True - right child gets False

# OK
class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        total = 0
        left = None
        stack = [root]
        while stack or left:
            if left:
                if left.left:
                    r = left.right
                    left = left.left
                    if r:
                        stack.append(r)
                else:
                    if left.right is None:
                        total += left.val
                    else:
                        stack.append(left.right)
                    left = None
                continue
            node = stack.pop()
            if node.left:
                left = node.left
            if node.right:
                stack.append(node.right)
        return total