# Sum of Left Leaves
**Difficulty:** EASY
[External](https://leetcode.com/problems/sum-of-left-leaves)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-left-leaves
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Grammarly](https://scaleengineer.com/companies/grammarly)
---
## Problem
Given the `root` of a binary tree, return _the sum of all left leaves._

A **leaf** is a node with no children. A **left leaf** is a leaf that is the left child of another node.

**Example 1:**

![](https://assets.glich.co/dsa/sum-of-left-leaves/image0.jpg) 

**Input:** root = [3,9,20,null,null,15,7]
**Output:** 24
**Explanation:** There are two left leaves in the binary tree, with values 9 and 15 respectively.

**Example 2:**

**Input:** root = [1]
**Output:** 0

**Constraints:**

* The number of nodes in the tree is in the range `[1, 1000]`.
* `-1000 <= Node.val <= 1000`

# Approaches
## Recursive Depth-First Search
This approach uses recursion to perform a depth-first traversal of the tree. The core idea is to define a function that, for any given node, calculates the sum of left leaves in the subtree rooted at that node. To identify a left leaf, we look ahead from a parent node. When at a node `curr`, we check its left child, `curr.left`. If `curr.left` exists and is a leaf (meaning it has no children), we've found a left leaf and add its value to our sum. We then recursively apply the same logic to the left and right subtrees to find all other left leaves.
**Time:** O(N), where N is the number of nodes in the tree. We must visit every node to check its children. · **Space:** O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** Code is concise and closely follows the recursive definition of a tree.; Easy to understand and implement.
**Cons:** Can lead to a `StackOverflowError` for very deep trees.; Function call overhead can be slightly less performant than an iterative solution.
### Explanation
This approach uses recursion to perform a depth-first traversal of the tree. The core idea is to define a function that, for any given node, calculates the sum of left leaves in the subtree rooted at that node.

To identify a left leaf, we don't check the current node itself. Instead, we look ahead from a parent node. When we are at a node `curr`, we check its left child, `curr.left`. If `curr.left` exists and is a leaf (meaning it has no children), we've found a left leaf and add its value to our sum. We then recursively apply the same logic to the left and right subtrees to find all other left leaves.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int sum = 0;
        // Check if the current node's left child is a leaf.
        if (root.left != null && root.left.left == null && root.left.right == null) {
            sum += root.left.val;
        }

        // Recursively find the sum in the left and right subtrees.
        sum += sumOfLeftLeaves(root.left);
        sum += sumOfLeftLeaves(root.right);

        return sum;
    }
}
```
### Algorithm
- Base Case: If the current node `root` is `null`, return 0.
- Initialize a local variable `sum` to 0.
- Check if the left child of the current node is a leaf. A node `n` is a leaf if `n.left == null` and `n.right == null`.
- If `root.left` is a leaf, add its value to `sum`.
- Recursively call the function on the left subtree (`root.left`) and add the returned value to `sum`.
- Recursively call the function on the right subtree (`root.right`) and add the returned value to `sum`.
- Return the total `sum`.

## Iterative Breadth-First Search with a Queue
An alternative iterative approach is to use Breadth-First Search (BFS), which explores the tree level by level. This method uses a queue instead of a stack. While the time complexity is the same as DFS, the space complexity depends on the maximum width of the tree, which can be more or less efficient than DFS depending on the tree's structure. The logic remains similar: we traverse the tree, and for each node we visit, we check if its left child is a leaf.
**Time:** O(N), as each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the tree. In the worst case of a complete binary tree, the last level can contain up to N/2 nodes, leading to O(N) space complexity.
**Pros:** Avoids recursion, thus preventing `StackOverflowError`.; Can be more space-efficient than DFS for very deep and narrow (skewed) trees.
**Cons:** Can use significantly more memory than DFS for wide, balanced trees.; The code is slightly more verbose than the recursive version.
### Explanation
An alternative iterative approach is to use Breadth-First Search (BFS), which explores the tree level by level. This method uses a queue instead of a stack. While the time complexity is the same as DFS, the space complexity depends on the maximum width of the tree, which can be more or less efficient than DFS depending on the tree's structure.

The logic remains similar: we traverse the tree, and for each node we visit, we check if its left child is a leaf. If so, we add its value to our running total.

```java
import java.util.Queue;
import java.util.LinkedList;

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

        int totalSum = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            // Check if the left child is a leaf
            if (node.left != null && node.left.left == null && node.left.right == null) {
                totalSum += node.left.val;
            }

            // Add children to the queue for the next level
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return totalSum;
    }
}
```
### Algorithm
- If `root` is `null`, return 0.
- Initialize `totalSum = 0`.
- Create a `Queue<TreeNode>` and offer the `root`.
- While the queue is not empty:
    - Poll a node `node` from the queue.
    - Check if `node.left` is a leaf. If it is, add `node.left.val` to `totalSum`.
    - If `node.left` is not `null`, offer it to the queue.
    - If `node.right` is not `null`, offer it to the queue.
- Return `totalSum`.

## Iterative Depth-First Search with a Stack
To avoid the potential for stack overflow in very deep trees and the overhead of recursive function calls, we can implement the DFS traversal iteratively using an explicit stack. This approach mirrors the logic of the recursive solution but manages the traversal manually. We start by pushing the root node onto a stack. Then, we loop as long as the stack is not empty. In each iteration, we pop a node, check if its left child is a leaf, and then push its non-null children onto the stack for future processing.
**Time:** O(N), as each node is pushed onto and popped from the stack exactly once. · **Space:** O(H), where H is the height of the tree. This space is used by the explicit stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** Avoids recursion and the risk of `StackOverflowError`.; Generally more space-efficient than BFS for typical (balanced) trees.; Directly translates the recursive logic into an iterative form.
**Cons:** Can use O(N) space for a skewed tree, which is its worst-case.; Slightly more complex to write than the recursive approach.
### Explanation
To avoid the potential for stack overflow in very deep trees and the overhead of recursive function calls, we can implement the DFS traversal iteratively using an explicit stack. This approach mirrors the logic of the recursive solution but manages the traversal manually.

We start by pushing the root node onto a stack. Then, we loop as long as the stack is not empty. In each iteration, we pop a node, check if its left child is a leaf (and add its value to the sum if so), and then push its non-null children (right then left, to process the left subtree first) onto the stack for future processing.

```java
import java.util.Stack;

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

        int totalSum = 0;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();

            // Check if the left child is a leaf
            if (node.left != null && node.left.left == null && node.left.right == null) {
                totalSum += node.left.val;
            }

            // Push children onto the stack for traversal
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return totalSum;
    }
}
```
### Algorithm
- If `root` is `null`, return 0.
- Initialize `totalSum = 0`.
- Create a `Stack<TreeNode>` and push the `root`.
- While the stack is not empty:
    - Pop a node `node` from the stack.
    - Check if `node.left` is a leaf. If it is, add `node.left.val` to `totalSum`.
    - If `node.right` is not `null`, push it onto the stack.
    - If `node.left` is not `null`, push it onto the stack.
- Return `totalSum`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int sumOfLeftLeaves ( TreeNode root ) { if ( root == null ) { return 0 ; } int res = 0 ; if ( root . left != null && root . left . left == null && root . left . right == null ) { res += root . left . val ; } res += sumOfLeftLeaves ( root . left ); res += sumOfLeftLeaves ( root . right ); return res ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int sumOfLeftLeaves ( TreeNode * root ) { if ( ! root ) { return 0 ; } int ans = sumOfLeftLeaves ( root -> right ); if ( root -> left ) { if ( ! root -> left -> left && ! root -> left -> right ) { ans += root -> left -> val ; } else { ans += sumOfLeftLeaves ( root -> left ); } } return ans ; } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def sumOfLeftLeaves ( self , root : TreeNode ) -> int : if root is None : return 0 res = 0 if root . left and root . left . left is None and root . left . right is None : res += root . left . val res += self . sumOfLeftLeaves ( root . left ) res += self . sumOfLeftLeaves ( root . right ) return res
```