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

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

JavaScript 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

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

/**
 * 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;
}

Python Alternative

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

1. Traverse tree:

   • Use DFS to visit all nodes
   • Can use pre-order, in-order, or post-order traversal

2. Identify left leaves:

   • A left leaf is a node that:
     • Is a leaf (has no children)
     • Is the left child of its parent

3. 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

4. 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

Related Problems

• 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