# 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:

```python
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

| Item | Meaning |
|---|---|
| Input | The root of a binary tree |
| Output | The sum of all left leaf values |
| Leaf node | A node with no children |
| Left leaf | A leaf that is the left child of its parent |

Example function shape:

```python
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}

```text
        3
       / \
      9   20
         /  \
        15   7
```

The left leaves are:

```python
9
15
```

Both are left children, and both are leaves.

So the answer is:

```python
9 + 15 = 24
```

Another example:

```text
    1
```

The tree contains only one node.

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

So the answer is:

```python
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:

```python
"is this node a left leaf?"
```

we can ask:

```python
"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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Every node is visited once |
| Space | `O(h)` | Recursive call stack height |

Where:

| Symbol | Meaning |
|---|---|
| `n` | Number of nodes |
| `h` | Height of the tree |

In the worst case of a skewed tree:

```python
h = n
```

In a balanced tree:

```python
h = log n
```

## Implementation

```python
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:

```python
dfs(node)
```

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

The base case is:

```python
if not node:
    return 0
```

An empty subtree contributes nothing.

We initialize:

```python
total = 0
```

Then we inspect the left child:

```python
if node.left:
```

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

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

If true, we add its value:

```python
total += left.val
```

Then we continue searching both subtrees:

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

Finally, we return the accumulated sum.

## Testing

```python
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

| Test | Why |
|---|---|
| Standard example tree | Checks multiple left leaves |
| Single-node tree | Root is not a left leaf |
| Mixed left and right leaves | Only left leaves should count |
| Tree with only right child | Result should be zero |
| Deep skewed tree | Checks recursive traversal depth |