Problem Description

You are given the root of a binary tree. Your task is to find and return the sum of all left leaves in the tree.

A leaf is defined as a node that has no children (both left and right children are null).

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

For example, in a binary tree, if a node has a left child that is a leaf (has no children of its own), then that left child's value should be included in the sum. However, if a node has a right child that is a leaf, that right child's value should NOT be included in the sum, as it's not a left leaf.

The goal is to traverse the entire tree, identify all nodes that are both:

1. Leaf nodes (no children)
2. Left children of their parent nodes

Then return the sum of the values of all such nodes. If there are no left leaves in the tree, return 0.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: While this is a binary tree problem, a tree is a special type of graph (specifically, a connected acyclic graph). Binary trees can be considered as graphs where each node has at most two children.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree. We have a root node, and each node has at most two children (left and right).

DFS

• Yes: We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using a DFS approach for solving the Sum of Left Leaves problem.

This makes sense because:

1. We need to traverse the entire tree to find all left leaves
2. We need to check each node's relationship with its parent (to determine if it's a left child)
3. We need to verify if each node is a leaf (has no children)
4. DFS allows us to recursively explore each subtree while maintaining the parent-child relationship context

The DFS pattern perfectly fits this problem as we can:

• Recursively traverse the tree
• Keep track of whether we're exploring a left or right subtree
• Check leaf conditions at each node
• Accumulate the sum of values that meet our criteria (left leaves)

Intuition

When we need to find the sum of all left leaves, we need to identify two key properties for each node: is it a leaf, and is it a left child of its parent?

The challenge is that a node doesn't know if it's a left or right child - only its parent knows this relationship. This means we need to check a node's children to determine if they are left leaves, rather than checking the node itself.

As we traverse the tree using DFS, at each node we can:

1. Look at our left child - if it exists and is a leaf (has no children), then we've found a left leaf and should add its value to our sum
2. Look at our right child - even if it's a leaf, we don't add it since it's not a left leaf

The recursive nature of DFS fits perfectly here. We can break down the problem into smaller subproblems:

• Calculate the sum of left leaves in the right subtree
• Check if the left child is a left leaf - if yes, add its value; if no, calculate the sum of left leaves in the left subtree
• Combine these results

A clever observation in the code is the condition root.left.left == root.left.right. When both children of a node are None, this condition evaluates to True (since None == None), elegantly identifying a leaf node without explicitly checking if both children are None.

This approach ensures we visit every node exactly once while maintaining the context needed to identify left leaves, giving us an efficient O(n) solution where n is the number of nodes in the tree.

Solution Approach

The solution implements a recursive DFS approach to traverse the binary tree and identify left leaves.

The algorithm starts by checking if the root is null. If it is, we return 0 since there are no nodes to process.

For a non-null root, we begin by recursively calculating the sum of all left leaves in the right subtree with self.sumOfLeftLeaves(root.right) and store this in our answer variable ans. We process the right subtree first, but the order doesn't matter since we're ultimately summing all left leaves.

Next, we examine the left child of the current node. If root.left exists, we need to determine if it's a leaf node:

• The condition root.left.left == root.left.right cleverly checks if both children are None. When a node is a leaf, both its left and right children are None, making this comparison evaluate to True
• If the left child is indeed a leaf, we add its value to ans with ans += root.left.val
• If the left child is not a leaf (has at least one child), we recursively calculate the sum of left leaves in the left subtree with ans += self.sumOfLeftLeaves(root.left)

The recursive calls continue to break down the tree into smaller subtrees, each following the same logic:

1. Process the right subtree recursively
2. Check if the left child is a left leaf or needs further exploration
3. Return the accumulated sum

This approach ensures every node is visited exactly once, giving us a time complexity of O(n) where n is the number of nodes. The space complexity is O(h) where h is the height of the tree, due to the recursive call stack.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm identifies and sums left leaves.

Consider this binary tree:

        3
       / \
      9   20
         /  \
        15   7

Step 1: Start at root (3)

• First, recursively process the right subtree (node 20)
• Then check the left child (node 9)

Step 2: Process right subtree from root (node 20)

• Recursively process its right subtree (node 7)
  • Node 7 has no children, so it returns 0
• Check its left child (node 15)
  • Node 15 has no children (15.left == 15.right → None == None → True)
  • Node 15 IS a left leaf! Add its value: 15
• Return 15 from this subtree

Step 3: Back at root (3), check left child (node 9)

• Node 9 exists and has no children (9.left == 9.right → None == None → True)
• Node 9 IS a left leaf! Add its value: 9

Step 4: Combine results

• Sum from right subtree: 15
• Sum from left child: 9
• Total: 15 + 9 = 24

The algorithm correctly identifies nodes 9 and 15 as left leaves (both are leaf nodes AND left children of their parents), while excluding node 7 (which is a leaf but a right child). The final answer is 24.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the binary tree. This is because the algorithm visits each node exactly once through the recursive traversal. At each node, it performs constant time operations (checking if a node exists, checking if it's a leaf, and adding to the sum).

The space complexity is O(n) in the worst case. This occurs when the tree is completely unbalanced (e.g., a skewed tree where each node has only one child), resulting in a recursion depth equal to the number of nodes. In the best case of a balanced tree, the space complexity would be O(log n) due to the recursion call stack, but we consider the worst-case scenario for space complexity analysis.

Note: The condition root.left.left == root.left.right is checking if both children are None (since None == None evaluates to True), which identifies a leaf node.

Common Pitfalls

1. Incorrectly Identifying Left Leaves

Pitfall: A common mistake is incorrectly identifying which nodes qualify as "left leaves." Developers often make one of these errors:

• Including the root node if it's a leaf (the root cannot be a left leaf since it has no parent)
• Including all leaf nodes regardless of whether they're left or right children
• Only checking if a node is on the left side of the tree, rather than checking if it's specifically a left child AND a leaf

Example of Incorrect Logic:

# WRONG: This counts all leaves, not just left leaves
def sumOfLeftLeaves(self, root):
    if not root:
        return 0
    if not root.left and not root.right:  # This is a leaf
        return root.val  # WRONG: might not be a LEFT leaf
    return self.sumOfLeftLeaves(root.left) + self.sumOfLeftLeaves(root.right)

Solution: Always check from the parent's perspective. A node is a left leaf only if:

1. It is the left child of its parent
2. It has no children of its own

The correct approach maintains context about whether we're examining a left or right child:

def sumOfLeftLeaves(self, root):
    def dfs(node, is_left):
        if not node:
            return 0
        # Check if this is a left leaf
        if not node.left and not node.right and is_left:
            return node.val
        # Recursively process children, marking left child appropriately
        return dfs(node.left, True) + dfs(node.right, False)
  
    return dfs(root, False)  # Root is not a left child

2. Using Ambiguous Leaf Detection

Pitfall: The original solution uses root.left.left == root.left.right to check if a node is a leaf. While this works when both children are None, it can be confusing and may lead to errors if the tree implementation changes or if someone misunderstands the logic.

Solution: Use explicit and clear conditions:

# Clear and explicit leaf check
if root.left and root.left.left is None and root.left.right is None:
    total_sum += root.left.val

This makes the code more readable and less prone to misinterpretation.

3. Edge Case Handling

Pitfall: Not properly handling edge cases such as:

• A tree with only one node (root only)
• A tree where all leaves are right children
• A skewed tree (all nodes form a single path)

Solution: Ensure your base cases and recursive logic handle these scenarios:

def sumOfLeftLeaves(self, root):
    if not root:
        return 0
  
    # Single node tree - root cannot be a left leaf
    if not root.left and not root.right:
        return 0
  
    total = 0
    # Only process left child if it exists
    if root.left:
        if not root.left.left and not root.left.right:
            total += root.left.val
        else:
            total += self.sumOfLeftLeaves(root.left)
  
    # Always process right subtree for potential left leaves within it
    total += self.sumOfLeftLeaves(root.right)
  
    return total