We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Left Leaves

Number: 404

Difficulty: Easy

Paid? No

Companies: Grammarly, Microsoft, Amazon, Bloomberg, Google, Meta, Yandex

Problem Description

Given the root of a binary tree, return 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.

Key Insights

  • Use recursion or iteration (DFS/BFS) to traverse the binary tree.
  • At each node, check if the left child is a leaf (has no children).
  • Sum up the values of all left leaves.
  • Ensure all nodes are checked, even if the immediate left child is not a leaf.

Space and Time Complexity

Time Complexity: O(n) where n is the number of nodes in the tree, because every node is visited exactly once. Space Complexity: O(n) in the worst case, due to recursion stack space if the tree is skewed.

Solution

We use a Depth-First Search (DFS) recursive approach. At each node, check if the left child exists and is a leaf. If so, add its value to the sum. Regardless, recursively call the function for both the left and right children (if applicable) to explore the entire tree. The base case for recursion is when the current node is null. This method ensures that all nodes are properly evaluated while maintaining clarity and simplicity.

Code Solutions

# 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

def sumOfLeftLeaves(root):
    # If the node is None, return 0 as there is nothing to add.
    if not root:
        return 0
    total = 0
    # Check if the left child exists and is a leaf.
    if root.left:
        if not root.left.left and not root.left.right:
            # If it's a left leaf, add its value.
            total += root.left.val
        else:
            # Otherwise, recursively check the left subtree.
            total += sumOfLeftLeaves(root.left)
    # Always traverse the right subtree.
    total += sumOfLeftLeaves(root.right)
    return total
← Back to All Questions