To solve the “Sum of Left Leaves in Binary Tree” problem, we can use a recursive approach to traverse the binary tree. During the traversal, we keep track of whether a node is a left leaf, and if it is, we add its value to the sum.

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

def sum_of_left_leaves(root: TreeNode) -> int:
    if not root:
        return 0

    left_sum = 0

    # Check if the left child is a leaf
    if root.left and not root.left.left and not root.left.right:
        left_sum += root.left.val

    # Recursively calculate the sum for left and right subtrees
    left_sum += sum_of_left_leaves(root.left)
    left_sum += sum_of_left_leaves(root.right)

    return left_sum

# Example usage:
root = TreeNode(6,
                TreeNode(8),
                TreeNode(12,
                         TreeNode(10),
                         TreeNode(5)
                         )
                )

result = sum_of_left_leaves(root)  # Sum of left leaves: 8 + 10 = 18
print(result)
assert result == 18

Explanation:

  • The sum_of_left_leaves function calculates the sum of left leaves in a binary tree.
  • If the current node has a left child and that left child is a leaf (has no left or right child), its value is added to the sum.
  • The function then recursively calculates the sum for the left and right subtrees.
  • The base case is when the current node is None, in which case the sum is 0.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. In the worst case, we need to visit every node once.

Space Complexity:

The space complexity is O(H), where H is the height of the binary tree. This is the maximum depth of the recursive call stack. In the worst case, the depth of the recursion is equal to the height of the tree.