Domain 1EasyCORE

Sum of Left Leaves

The problem requires finding the sum of all left leaves in a given binary tree. A left leaf is defined as a node that does not have any children (i.e., it is a leaf) and is located on the left side of its parent node.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

404. Sum of Left Leaves

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 52.3%


Problem Breakdown

The problem requires finding the sum of all left leaves in a given binary tree. A left leaf is defined as a node that does not have any children (i.e., it is a leaf) and is located on the left side of its parent node.

Inputs:

  • A binary tree represented by its root node.

Outputs:

  • An integer representing the sum of all left leaves in the tree.

Implicit Constraints or Tricky Edge Cases:

  • The tree could be empty (root is None).
  • The tree could have only one node, which might not be a leaf.
  • All nodes are assumed to have non-negative values.

Intuition

The brute-force approach would involve traversing the entire tree and checking each node to see if it is a left leaf. This would require visiting every node in the tree, leading to a time complexity of O(n), where n is the number of nodes in the tree. However, this approach does not leverage any specific properties of binary trees that could simplify the solution.

A better approach involves using a depth-first search (DFS) traversal, specifically a pre-order traversal, to efficiently identify left leaves. By keeping track of whether a node is a left child during the traversal, we can directly sum up the values of all left leaves without unnecessary checks.

Approach

We will use a recursive DFS approach to traverse the binary tree. The key insight is to pass an additional parameter indicating whether the current node is a left child. During the traversal:

  1. If the current node is None, return 0.
  2. If the current node is a leaf (i.e., it has no left or right children) and it is a left child, return its value.
  3. Recursively sum the values of left leaves in the left subtree by passing True to indicate that the next node will be a left child.
  4. Recursively sum the values of left leaves in the right subtree by passing False to indicate that the next node will not be a left child.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack, which can go as deep as the height of the tree.

Solution

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

def sumOfLeftLeaves(root: TreeNode) -> int:
    def dfs(node: TreeNode, is_left: bool) -> int:
        if not node:
            return 0
        if not node.left and not node.right:
            return node.val if is_left else 0
        left_sum = dfs(node.left, True)
        right_sum = dfs(node.right, False)
        return left_sum + right_sum
    
    return dfs(root, False)

Edge Cases Handled

  • Empty Tree: If the input tree is empty (root is None), the function returns 0 immediately.
  • Single Node Tree: If the tree has only one node and it is not a leaf, the function returns 0. If it is a leaf, it returns its value if it is a left child (which it cannot be in this case since there are no other nodes).
  • All Nodes as Left Leaves: The function correctly sums all left leaves regardless of their position in the tree.
  • No Left Leaves: If there are no left leaves in the tree, the function returns 0.