Sum of Left Leaves

Difficulty: Easy | Acceptance: 62.70% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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

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

• Examples
• Constraints
• Depth-First Search (Recursive)
• Breadth-First Search (Iterative)
• Depth-First Search (Iterative with Stack)

Examples

Example 1:

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

Depth-First Search (Recursive)

Intuition We traverse the tree recursively. For each node, we check if its left child is a leaf. If it is, we add its value to the sum. Then we continue the traversal on both the left and right subtrees.

Steps

• If the root is null, return 0.
• Check if the left child of the current node exists and is a leaf (both left and right children are null).
• If the left child is a leaf, add its value to the result of the recursive call on the right subtree.
• Otherwise, return the sum of recursive calls on both left and right subtrees.

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        if root.left and not root.left.left and not root.left.right:
            return root.left.val + self.sumOfLeftLeaves(root.right)
        
        return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

Complexity

• Time: O(N) where N is the number of nodes in the tree.
• Space: O(H) where H is the height of the tree, due to the recursion stack. In the worst case, H can be N.
• Notes: This approach is concise and leverages the call stack for traversal.

Breadth-First Search (Iterative)

Intuition We use a queue to perform a level-order traversal. As we process each node, we inspect its left child. If the left child is a leaf, we add its value to the sum. Otherwise, we add the left child to the queue for further processing. We always add the right child to the queue if it exists.

Steps

• Initialize a queue with the root node.
• While the queue is not empty:
  • Dequeue a node.
  • If the node has a left child:
    • Check if it is a leaf. If yes, add value to sum.
    • If no, enqueue the left child.
  • If the node has a right child, enqueue it.
• Return the accumulated sum.

from collections import deque

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = deque([root])
        total = 0
        
        while queue:
            node = queue.popleft()
            
            if node.left:
                if not node.left.left and not node.left.right:
                    total += node.left.val
                else:
                    queue.append(node.left)
            
            if node.right:
                queue.append(node.right)
        
        return total

Complexity

• Time: O(N) where N is the number of nodes in the tree.
• Space: O(W) where W is the maximum width of the tree (maximum number of nodes at any level).
• Notes: Iterative approach avoids potential stack overflow issues with very deep trees.

Depth-First Search (Iterative with Stack)

Intuition We simulate the recursive DFS using an explicit stack. To determine if a node is a left leaf, we need to know if it is a left child of its parent. We can store a boolean flag along with the node in the stack indicating whether it is a left child.

Steps

• Initialize a stack with the root node and a flag set to false.
• While the stack is not empty:
  • Pop a node and its isLeft flag.
  • If the node is a leaf (no children) and isLeft is true, add its value to the sum.
  • Push the right child onto the stack with flag false.
  • Push the left child onto the stack with flag true.
• Return the accumulated sum.

class Solution:
    def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        stack = [(root, False)]
        total = 0
        
        while stack:
            node, is_left = stack.pop()
            
            if not node.left and not node.right and is_left:
                total += node.val
            
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, True))
        
        return total

Complexity

• Time: O(N) where N is the number of nodes in the tree.
• Space: O(H) where H is the height of the tree, for the stack.
• Notes: This approach gives fine-grained control over the traversal order and avoids recursion overhead.