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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Left Leaves

Difficulty: Easy

Problem Description

Given the root of a binary tree, return the sum of all left leaves. A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Key Insights

  • A left leaf is defined as a leaf node that is the left child of its parent.
  • We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the tree.
  • When traversing, we need to check if a node is a leaf and if it is a left child to accumulate its value.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as we may need to visit all nodes. Space Complexity: O(h) - where h is the height of the tree, which is the space required for the recursion stack in DFS.

Solution

To solve the problem, we can use a Depth-First Search (DFS) approach. We will recursively traverse the tree and keep track of whether the current node is a left child. If we encounter a leaf node that is a left child, we will add its value to our sum.

We will use a helper function that takes the current node and a boolean indicating whether it is a left child. If the current node is null, we return 0. If it is a left leaf, we return its value. Otherwise, we continue traversing the left and right subtrees.

Code Solutions

def sumOfLeftLeaves(root):
    def dfs(node, is_left):
        if not node:
            return 0
        if not node.left and not node.right:  # Check if it's a leaf
            return node.val if is_left else 0
        return dfs(node.left, True) + dfs(node.right, False)  # Recur for left and right children

    return dfs(root, False)
← Back to All Questions