You are given the root of a binary tree. Your task:

Return the sum of all left leaves.

Definitions:

• A leaf is a node with no children.
• A left leaf is a leaf that is the left child of its parent.

Example:

Input:
    3
   / \
  9  20
     / \
    15  7

Output: 24
Explanation: left leaves are 9 and 15 → 9 + 15 = 24

Another example:

Input:
  1
   \
    2
Output: 0
(no left leaves)

---

Problem Understanding

You must walk through the tree and identify leaf nodes, but only those that:

1. Are left children
2. Have no left or right children

Important clarifications:

• Not all left children are left leaves
• A leaf on the right side should not be counted
• The root is never considered a leaf (it has no parent)

---

Logic Explained in Simple English

The simplest way to think about solving this:

1. Traverse the tree (DFS or BFS)
2. For each node, check if:
   • it has a left child
   • that left child has no children
   • if yes → add its value to the answer
3. Recursively continue into left and right subtrees
4. Return accumulated sum

Why this works:

• We only count when explicitly detecting a left child that is a leaf
• Recursion naturally visits all nodes
• No extra storage is needed

Alternate way of thinking:

• Pass a boolean flag indicating whether the current node is a left child
• When reaching a leaf:
  • If it is left → add value
  • Otherwise ignore

Both approaches are valid.

---

Step-by-Step Approach

We’ll use the first approach (check left child condition):

1. If root is null → return 0
2. Initialize sum = 0
3. If root.left exists and is a leaf → add root.left.val to sum
4. Recurse into left subtree
5. Recurse into right subtree
6. Return sum

A node is a leaf if:

node.left == null && node.right == null

---

Java Implementation

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) return 0;
        int sum = 0;

        if (root.left != null && isLeaf(root.left)) {
            sum += root.left.val;
        }

        sum += sumOfLeftLeaves(root.left);
        sum += sumOfLeftLeaves(root.right);

        return sum;
    }

    private boolean isLeaf(TreeNode node) {
        return node.left == null && node.right == null;
    }
}

---

Dry Run Example

Tree:

      3
     / \
    9   20
        / \
       15  7

Start at root (3)

• left child exists (9)
• 9 is a leaf → add 9
• recurse left and right

Recurse into left subtree (9)

• node is leaf but NOT a left child of its parent here → contributes 0

Recurse into right subtree (20)

• left child exists (15)
• 15 is leaf → add 15
• recurse left and right

Recurse into 15

• leaf, but counted already (no extra)

Recurse into 7

• leaf but right child → ignore

Total = 9 + 15 = 24

Output:

24

---

Time and Space Complexity

Time Complexity

O(n)

Every node visited once.

Space Complexity

O(h)

Where h = tree height (worst O(n) for skewed tree, best O(log n) for balanced).

---

Common Mistakes and How to Avoid Them

Mistake 1: Counting all left children

Must verify leaf condition.

Mistake 2: Counting right leaves

Right leaves are ignored.

Mistake 3: Treating root as a leaf

Root has no parent, never count it.

Mistake 4: Forgetting recursion both sides

Must explore full tree.

Mistake 5: Using global sum incorrectly

Functional return approach avoids state bugs.