Sum of Left Leaves

Given a binary tree, return the sum of all left leaves of the tree.

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

Example(s)

Example 1:

Input:
    5
   / \
  2   12
     /  \
    3    8

Output: 5
Explanation:
Left leaves: 2 (left child of 5) and 3 (left child of 12)
Sum: 2 + 3 = 5

Example 2:

Input:
       2
      / \
    4    2
   / \ 
  3   9 

Output: 3
Explanation:
Left leaves: 3 (left child of 4)
Note: 4 is not a leaf, and 9 is a right child
Sum: 3

Example 3:

Input:
    1
   / \
  2   3

Output: 2
Explanation:
Left leaf: 2 (left child of 1)
Sum: 2

Example 4:

Input:
    1

Output: 0
Explanation:
No left leaves (only root node).

Solution

The solution uses DFS (Depth-First Search):

Traverse tree: Use DFS to visit all nodes
Check left child: For each node, check if it has a left child
Check if leaf: If left child exists and is a leaf, add its value
Recursive: Process both left and right subtrees

JavaScript Solution
Python Solution

JavaScript Solution - DFS

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Find sum of all left leaves
* @param {TreeNode} root - Root of binary tree
* @return {number} - Sum of left leaves
*/
function sumOfLeftLeaves(root) {
if (!root) return 0;

let sum = 0;

/**
 * Helper function to check if node is a leaf
 */
function isLeaf(node) {
  return node && !node.left && !node.right;
}

/**
 * DFS function
 * @param {TreeNode} node - Current node
 * @param {boolean} isLeft - Whether current node is a left child
 */
function dfs(node, isLeft) {
  if (!node) return;
  
  // If current node is a left leaf, add its value
  if (isLeft && isLeaf(node)) {
    sum += node.val;
    return;
  }
  
  // Recursively process left and right children
  dfs(node.left, true);   // Left child
  dfs(node.right, false); // Right child
}

dfs(root, false); // Root is not a left child
return sum;
}

// Helper function to create tree nodes for testing
function TreeNode(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}

// Test cases
// Example 1: [5, 2, 12, null, null, 3, 8]
const tree1 = new TreeNode(5,
new TreeNode(2),
new TreeNode(12,
  new TreeNode(3),
  new TreeNode(8)
)
);
console.log('Example 1:', sumOfLeftLeaves(tree1)); // 5

// Example 2: [2, 4, 2, 3, 9]
const tree2 = new TreeNode(2,
new TreeNode(4,
  new TreeNode(3),
  new TreeNode(9)
),
new TreeNode(2)
);
console.log('Example 2:', sumOfLeftLeaves(tree2)); // 3

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

def sum_of_left_leaves(root: Optional[TreeNode]) -> int:
  """
  Find sum of all left leaves
  
  Args:
      root: Root of binary tree
      
  Returns:
      int: Sum of left leaves
  """
  if not root:
      return 0
  
  total = 0
  
  def is_leaf(node: Optional[TreeNode]) -> bool:
      """Check if node is a leaf"""
      return node and not node.left and not node.right
  
  def dfs(node: Optional[TreeNode], is_left: bool):
      """
      DFS function
      
      Args:
          node: Current node
          is_left: Whether current node is a left child
      """
      if not node:
          return
      
      # If current node is a left leaf, add its value
      if is_left and is_leaf(node):
          nonlocal total
          total += node.val
          return
      
      # Recursively process left and right children
      dfs(node.left, True)   # Left child
      dfs(node.right, False) # Right child
  
  dfs(root, False)  # Root is not a left child
  return total

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

# Test cases
# Example 1: [5, 2, 12, None, None, 3, 8]
tree1 = TreeNode(5,
  TreeNode(2),
  TreeNode(12,
      TreeNode(3),
      TreeNode(8)
  )
)
print('Example 1:', sum_of_left_leaves(tree1))  # 5

# Example 2: [2, 4, 2, 3, 9]
tree2 = TreeNode(2,
  TreeNode(4,
      TreeNode(3),
      TreeNode(9)
  ),
  TreeNode(2)
)
print('Example 2:', sum_of_left_leaves(tree2))  # 3

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Without Helper Flag)

Here's an alternative approach that checks the parent's left child:

JavaScript Alternative
Python Alternative

/**
 * Alternative: Check parent's left child
 */
function sumOfLeftLeavesAlternative(root) {
  if (!root) return 0;
  
  let sum = 0;
  
  function dfs(node) {
    if (!node) return;
    
    // Check if left child exists and is a leaf
    if (node.left && !node.left.left && !node.left.right) {
      sum += node.left.val;
    }
    
    // Recursively process both subtrees
    dfs(node.left);
    dfs(node.right);
  }
  
  dfs(root);
  return sum;
}

def sum_of_left_leaves_alternative(root: Optional[TreeNode]) -> int:
    """
    Alternative: Check parent's left child
    """
    if not root:
        return 0
    
    total = 0
    
    def dfs(node: Optional[TreeNode]):
        if not node:
            return
        
        # Check if left child exists and is a leaf
        if node.left and not node.left.left and not node.left.right:
            nonlocal total
            total += node.left.val
        
        # Recursively process both subtrees
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return total

Complexity

Time Complexity: O(n) - Where n is the number of nodes in the tree. We visit each node once.
Space Complexity: O(h) - Where h is the height of the tree. For the recursion stack. In worst case (skewed tree), O(n). In average case (balanced tree), O(log n).

Approach

The solution uses DFS (Depth-First Search):

Traverse tree:
- Use DFS to visit all nodes
- Can use pre-order, in-order, or post-order traversal
Identify left leaves:
- A left leaf is a node that:
  - Is a leaf (has no children)
  - Is the left child of its parent
Two approaches:
- Approach 1: Pass a flag indicating if current node is a left child
- Approach 2: Check if current node's left child is a leaf
Sum accumulation:
- When we find a left leaf, add its value to the sum
- Continue traversing to find all left leaves

Key Insights

DFS traversal: Visit all nodes to find left leaves
Left leaf definition: Must be both a leaf AND a left child
Two approaches: Flag-based or parent-check based
O(n) time: Must visit all nodes
O(h) space: Recursion stack depth

Step-by-Step Example

Let's trace through Example 1:

Tree:
    5
   / \
  2   12
     /  \
    3    8

DFS traversal with flag:

dfs(5, false):
  isLeft = false, not a left child
  Check: isLeft && isLeaf(5)? No (not left child)
  dfs(2, true):
    isLeft = true, is a left child
    Check: isLeft && isLeaf(2)? Yes! (left child and leaf)
      sum += 2, sum = 2
  dfs(12, false):
    isLeft = false, not a left child
    Check: isLeft && isLeaf(12)? No (not left child)
    dfs(3, true):
      isLeft = true, is a left child
      Check: isLeft && isLeaf(3)? Yes! (left child and leaf)
        sum += 3, sum = 5
    dfs(8, false):
      isLeft = false, not a left child
      Check: isLeft && isLeaf(8)? No (not left child)

Result: sum = 5

Visual Representation

Example 1:
    5
   / \
  2   12
     /  \
    3    8

Left leaves:
  - Node 2: left child of 5, is a leaf → value 2
  - Node 3: left child of 12, is a leaf → value 3
  - Node 8: right child of 12, not a left leaf

Sum: 2 + 3 = 5 ✓

Example 2:
       2
      / \
    4    2
   / \ 
  3   9 

Left leaves:
  - Node 3: left child of 4, is a leaf → value 3
  - Node 4: left child of 2, but NOT a leaf (has children)
  - Node 9: right child of 4, not a left leaf

Sum: 3 ✓

Edge Cases

Empty tree: Return 0
Single node: Return 0 (root is not a left child)
No left leaves: Return 0
All left leaves: Sum all left leaf values
Skewed tree: Still works correctly

Important Notes

Left leaf definition: Must be BOTH a leaf AND a left child
Root is not left: Root node is never a left child
Right leaves don't count: Only left leaves are included
O(n) time: Must visit all nodes
O(h) space: Recursion stack

Why DFS Works

Key insight:

We need to visit all nodes to find left leaves
DFS systematically visits all nodes
We can identify left leaves by checking:
- If node is a leaf (no children)
- If node is a left child (passed as flag or checked from parent)

Traversal order:

Any DFS order works (pre-order, in-order, post-order)
We just need to visit all nodes and check the left leaf condition

Sum of Left Leaves: This problem
Maximum Depth of Binary Tree: Different tree problem
Binary Tree Level Order Traversal: Different traversal
Path Sum: Different tree problem

Takeaways

DFS traversal visits all nodes
Left leaf check requires both leaf and left child conditions
O(n) time to visit all nodes
O(h) space for recursion stack
Classic tree traversal problem with condition checking

Example(s)​

Solution​

JavaScript Solution - DFS

Output:

Python Solution - DFS

Output:

Alternative Solution (Without Helper Flag)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Visual Representation​

Edge Cases​

Important Notes​

Why DFS Works​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Without Helper Flag)

Complexity

Approach

Key Insights

Step-by-Step Example

Visual Representation

Edge Cases

Important Notes

Why DFS Works

Related Problems

Takeaways