#404

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Sum of Left Leaves

Compute the total of all left leaves in a binary tree using precise traversal and state tracking techniques for correctness.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree, compute the sum of all nodes that are left leaves. A leaf is a node with no children, and a left leaf is a leaf that is the left child of its parent.

For example, given root = [3,9,20,null,null,15,7], the left leaves are nodes with values 9 and 15, resulting in a sum of 24. Constraints: the number of nodes is 1 to 1000, and each node value ranges from -1000 to 1000.

Examples

Example 1

Input: root = [3,9,20,null,null,15,7]

Output: 24

There are two left leaves in the binary tree, with values 9 and 15 respectively.

Example 2

Input: root = [1]

Output: 0

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 1000].
-1000 <= Node.val <= 1000

Solution Approach

Depth-First Search (DFS) Recursion

Recursively traverse the tree, passing a flag that indicates whether the current node is a left child. If a node is a leaf and the flag is true, add its value to the sum. Combine results from left and right subtrees for the final sum.

Breadth-First Search (BFS) Iteration

Use a queue to traverse the tree level by level. Track whether each node is a left child. When encountering a leaf that is a left child, increment the sum. Continue until all nodes are processed.

State Tracking Optimization

Maintain a running sum during traversal instead of collecting all left leaves. This avoids unnecessary storage and reduces memory usage while ensuring each left leaf contributes exactly once to the total.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) since each node is visited once, and space complexity is O(h) for recursion stack in DFS or O(n) for BFS queue, where h is tree height and n is number of nodes.

What Interviewers Usually Probe

Ask for traversal strategy before coding.
Probe how to identify left leaves without extra storage.
Expect handling of edge cases like single-node or all-right-child trees.

Common Pitfalls or Variants

Common pitfalls

Confusing left children with left leaves and summing non-leaf nodes.
Forgetting to check for null nodes in recursive or iterative traversal.
Mixing DFS and BFS state tracking, causing incorrect sums in deeper subtrees.

Follow-up variants

Sum of right leaves instead of left leaves using similar traversal.
Compute sum of leaves at odd tree levels only, requiring level tracking.
Sum all leaves without distinguishing left or right child, simplifying state management.

FAQ

What defines a left leaf in this problem?

A left leaf is a node with no children that is the left child of its parent.

Can I use BFS instead of DFS for Sum of Left Leaves?

Yes, BFS works as long as you track whether each node is a left child and check for leaf nodes before adding to the sum.

How do I handle a tree with only the root node?

The root is not a left child, so the sum of left leaves is 0 in this case.

What is the time and space complexity of the standard approach?

Time complexity is O(n) because every node is visited once; space is O(h) for DFS recursion or O(n) for BFS queue, with h as tree height.

Does this problem require tracking parent nodes?

Not explicitly; you only need to know if a node is a left child while traversing to correctly identify left leaves.

terminal

Solution

Solution 1: Recursion

First, we check if `root` is null. If it is, we return $0$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        ans = self.sumOfLeftLeaves(root.right)
        if root.left:
            if root.left.left == root.left.right:
                ans += root.left.val
            else:
                ans += self.sumOfLeftLeaves(root.left)
        return ans

Solution 2: Stack

We can also convert the recursion in Solution 1 to iteration, using a stack to simulate the recursion process.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        ans = self.sumOfLeftLeaves(root.right)
        if root.left:
            if root.left.left == root.left.right:
                ans += root.left.val
            else:
                ans += self.sumOfLeftLeaves(root.left)
        return ans

Continue Practicing

#449 serialize and deserialize bst #297 serialize and deserialize binary tree #513 find bottom left tree value