LeetCode 404: Sum of Left Leaves

Problem Restatement

We are given the root of a binary tree.

A leaf node is a node with no children:

node.left is None and node.right is None

A left leaf is a leaf node that is also the left child of its parent.

We must return the sum of all left leaves in the tree.

Input and Output

Example function shape:

def sumOfLeftLeaves(root: Optional[TreeNode]) -> int:
    ...

Examples

Consider this tree:

image_group{“layout”:“carousel”,“aspect_ratio”:“16:9”,“query”:[“binary tree left leaves example diagram”,“sum of left leaves leetcode 404 tree”,“binary tree left leaf illustration”,“tree traversal left leaf example”],“num_per_query”:1}

        3
       / \
      9   20
         /  \
        15   7

The left leaves are:

9
15

Both are left children, and both are leaves.

So the answer is:

9 + 15 = 24

Another example:

    1

The tree contains only one node.

The root is not considered a left leaf because it has no parent.

So the answer is:

0

First Thought: Traverse Every Node

We can visit every node in the tree.

For each node:

1. Check whether its left child exists.
2. Check whether that left child is a leaf.
3. If yes, add its value to the answer.
4. Continue traversing the tree.

This naturally suggests depth-first search.

Key Insight

A node itself does not know whether it is a left child.

That information comes from its parent.

So instead of asking:

"is this node a left leaf?"

we can ask:

"does this node have a left child that is a leaf?"

This makes the recursion simpler.

At each node:

1. Inspect the left child.
2. Add its value if it is a leaf.
3. Recurse into both subtrees.

Algorithm

Define a recursive DFS function.

For each node:

1. If the node is None, return 0.
2. Initialize the current contribution as 0.
3. If the node has a left child:
   • Check whether that child is a leaf.
   • If yes, add its value.
4. Recurse into the left subtree.
5. Recurse into the right subtree.
6. Return the total sum.

Correctness

We prove that the algorithm returns the sum of all left leaves in the tree.

For every node in the tree, the algorithm checks whether its left child exists and whether that left child is a leaf.

A node is a left leaf exactly when:

it is a left child
and
it has no children

The algorithm identifies such nodes precisely by inspecting the left child of each parent node.

If a left child is a leaf, its value is added exactly once.

No right leaf is added, because the algorithm only checks left children.

No non-leaf node is added, because the algorithm requires both children to be None.

The recursive traversal visits every node in the tree, so every possible left leaf is checked.

Therefore, the returned sum is correct.

Complexity

Where:

In the worst case of a skewed tree:

h = n

In a balanced tree:

h = log n

Implementation

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            total = 0

            if node.left:
                left = node.left

                if left.left is None and left.right is None:
                    total += left.val

            total += dfs(node.left)
            total += dfs(node.right)

            return total

        return dfs(root)

Code Explanation

We define a recursive helper:

dfs(node)

This returns the sum of left leaves inside the subtree rooted at node.

The base case is:

if not node:
    return 0

An empty subtree contributes nothing.

We initialize:

total = 0

Then we inspect the left child:

if node.left:

If it exists, we check whether it is a leaf:

if left.left is None and left.right is None:

If true, we add its value:

total += left.val

Then we continue searching both subtrees:

total += dfs(node.left)
total += dfs(node.right)

Finally, we return the accumulated sum.

Testing

def test_sum_of_left_leaves():
    s = Solution()

    root1 = TreeNode(
        3,
        TreeNode(9),
        TreeNode(
            20,
            TreeNode(15),
            TreeNode(7),
        ),
    )

    assert s.sumOfLeftLeaves(root1) == 24

    root2 = TreeNode(1)

    assert s.sumOfLeftLeaves(root2) == 0

    root3 = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(4),
            TreeNode(5),
        ),
        TreeNode(3),
    )

    assert s.sumOfLeftLeaves(root3) == 4

    root4 = TreeNode(
        1,
        None,
        TreeNode(2),
    )

    assert s.sumOfLeftLeaves(root4) == 0

    root5 = TreeNode(
        1,
        TreeNode(
            2,
            TreeNode(
                3,
                TreeNode(4),
                None,
            ),
            None,
        ),
        None,
    )

    assert s.sumOfLeftLeaves(root5) == 4

    print("all tests passed")

Test Notes