Code Implementation

# 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

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        if not root:
            return 0

        def is_leaf(node):
            return node and not node.left and not node.right

        total = 0
        if root.left:
            if is_leaf(root.left):
                total += root.left.val
            else:
                total += self.sumOfLeftLeaves(root.left)
        if root.right:
            total += self.sumOfLeftLeaves(root.right)
        return total
      

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

// 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 total = 0;
        if (root.left != null) {
            if (root.left.left == null && root.left.right == null)
                total += root.left.val;
            else
                total += sumOfLeftLeaves(root.left);
        }
        if (root.right != null)
            total += sumOfLeftLeaves(root.right);
        return total;
    }
}
      

/**
 * 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumOfLeftLeaves = function(root) {
    if (!root) return 0;
    let total = 0;
    if (root.left) {
        if (!root.left.left && !root.left.right)
            total += root.left.val;
        else
            total += sumOfLeftLeaves(root.left);
    }
    if (root.right)
        total += sumOfLeftLeaves(root.right);
    return total;
};
      

Problem Description

Given the root of a binary tree, your task is to find the sum of all left leaves. A left leaf is a node that is the left child of its parent and does not have any children (i.e., both its left and right pointers are null). The tree can have any structure, and you need to return the sum of the values of all such left leaves.

• There is exactly one valid answer for each input tree.
• You must not reuse nodes; only count each left leaf once.
• Return 0 if there are no left leaves in the tree.

Thought Process

To solve this problem, we first need to understand what constitutes a "left leaf." We are only interested in nodes that:

• Are the left child of their parent
• Have no left or right children (i.e., they are leaves)

We also need to decide between recursion and iteration. Recursion is a natural fit for tree problems, as it allows us to handle each subtree in a similar way. We'll also consider how to avoid double-counting or missing any left leaves.

Solution Approach

We'll use a recursive approach to traverse the tree. Here’s how we can break down the solution:

1. Base Case: If the current node is null, return 0. This handles empty trees and recursion end points.
2. Check for Left Leaf: If the current node has a left child, check if that left child is a leaf (i.e., both its left and right are null).
   • If it is a leaf, add its value to the total sum.
   • If not, recursively call the function on the left child to continue searching.
3. Recurse on the Right Subtree: Always recursively call the function on the right child, since a left leaf could exist further down in the right subtree.
4. Combine Results: Add up the sums from left and right subtrees and return the total.

This approach ensures that every left leaf is counted exactly once, and the function visits each node only as needed.

Example Walkthrough

Let's consider the following binary tree:

        3
       / \
      9  20
         / \
        15  7
  

• The left child of 3 is 9, which has no children. So, 9 is a left leaf.
• Node 20 has a left child 15, which is also a leaf (no children). So, 15 is another left leaf.
• Node 7 is not a left child, so it doesn't count.

The sum of left leaves is 9 + 15 = 24.

Step-by-step:

1. Start at 3. Its left child is 9 (a leaf) → add 9.
2. Move to right child (20). Its left child is 15 (a leaf) → add 15.
3. Right child of 20 is 7 (not a left child) → ignore.
4. No more nodes. Total sum is 24.

Time and Space Complexity

Brute-force approach: Traversing every node and checking if it is a left leaf would take O(n) time, where n is the number of nodes. There is no way to do better since each node must be checked at least once.

Optimized recursive approach: Still O(n) time, as every node is visited once. Space complexity is O(h), where h is the height of the tree, due to the call stack in recursion. For a balanced tree, h = log n; for a skewed tree, h = n.

Summary

The "Sum of Left Leaves" problem is a classic binary tree traversal challenge. By understanding the definition of a left leaf and using recursion, we efficiently sum the values of all left leaves. The solution is elegant because it leverages the natural structure of trees and recursion, ensuring each node is visited only as necessary. The approach is both simple and optimal for time and space complexity.