Sum of Left Leaves: Recursive Tree Traversal

You are given the root of a binary tree. Return the sum of all left leaves. A left leaf is a node that has no children and is the left child of its parent. This is LeetCode 404: Sum of Left Leaves, and despite being easy, it forces you to think carefully about what information the parent has that the child does not.

The approach: DFS with parent context

The key insight is that a node cannot know whether it is a left child by looking at itself alone. Only the parent knows. When you recurse into a left child, you are the one who knows it is on the left side. So the decision to add a value to the sum must happen at the parent level, not the child level.

Here is the pattern: at each node, check if its left child exists and is a leaf (no children of its own). If so, add that child's value. Then recurse into both subtrees to collect more left leaves deeper in the tree.

The algorithm works in three parts:

1. If the current node is None, return 0.
2. If the current node has a left child that is a leaf, add that child's value to the result.
3. Recurse into both left and right subtrees and sum up whatever they return.

def sum_of_left_leaves(root):
    if root is None:
        return 0

    total = 0
    if root.left and not root.left.left and not root.left.right:
        total += root.left.val
    else:
        total += sum_of_left_leaves(root.left)

    total += sum_of_left_leaves(root.right)
    return total

Complexity

Time is O(n) because you visit every node in the tree exactly once. Each visit does constant work: check if the left child is a leaf, then recurse.

Space is O(h) where h is the height of the tree. This comes from the recursion call stack. For a balanced tree, h is log n. For a skewed tree that looks like a linked list, h equals n.

The building blocks

Parent-level decision making. The fundamental skill here is recognizing that the parent, not the child, has the context needed to make a decision. The child does not know whether it is a left or right child. The parent does. This shows up in many tree problems where you need to treat left and right children differently, like printing boundary nodes or finding the leftmost value at each level.

Leaf detection. A leaf is a node with no left child and no right child. You check not node.left and not node.right. This is a basic building block, but forgetting it leads to bugs. Some people check node is None instead, which tests for a missing node, not a leaf.

Recursive accumulation. You collect values from both subtrees and combine them with addition. The recursion returns a number from each subtree, and the parent sums them. This pattern (recurse left, recurse right, combine) is the same skeleton used in problems like Maximum Depth and Diameter of Binary Tree.

Edge cases

• Empty tree (root is None): return 0. There are no nodes at all, so no left leaves.
• Single node (root is a leaf): return 0. The root has no parent, so it cannot be a left child. It is not counted.
• Root has only a left child that is a leaf: return that child's value. This is the simplest non-trivial case.
• Tree with no left leaves: all leaves are right children. The function returns 0 because none of the leaf checks at the parent level ever trigger.

From understanding to recall

You just walked through a clean recursive solution where the parent checks whether its left child is a leaf. The logic is simple: look left, check for a leaf, add the value, then recurse deeper. You understand why the check happens at the parent and not at the leaf itself.

But understanding is not the same as recall. In an interview, you need to produce this solution from scratch. You need to remember that the parent holds the context, that you check not node.left.left and not node.left.right to detect a leaf, and that you handle the left and right subtrees differently in the recursion. These details are easy to fumble under pressure.

Spaced repetition locks it in. You practice writing the solution from memory at increasing intervals. After a few rounds, the parent-level leaf check becomes automatic, and you no longer need to re-derive it on the spot.

Related posts

• Maximum Depth of Binary Tree - Classic DFS tree problem
• Path Sum - Another tree problem tracking values during traversal
• Invert Binary Tree - Recursive tree transformation