LeetCode 404 - Sum of Left Leaves

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem gives us the root node of a binary tree and asks us to compute the sum of all left leaves in the tree.

A binary tree node may have up to two children, a left child and a right child. A leaf node is a node that has no children at all, meaning both its left and right pointers are None in Python or nil in Go.

The important detail is that not every left child counts toward the answer. A node contributes to the sum only if both of these conditions are true:

The node is the left child of its parent.
The node is a leaf node.

For example, consider this tree:

Node 9 is a left child and also a leaf, so it contributes to the sum. Node 15 is also a left child and a leaf, so it contributes as well. Node 20 is a right child and not a leaf, so it does not count. Node 7 is a right leaf, so it also does not count.

The expected output is the total sum of all such left leaves.

The constraints tell us that the number of nodes is between 1 and 1000. This is a relatively small tree, so an O(n) traversal is more than sufficient. Since every node may need to be inspected at least once to determine whether it is a left leaf, linear time is effectively optimal.

Several edge cases are important:

A tree with only one node has no parent-child relationships, so there cannot be any left leaves.
A left child that itself has children is not a leaf and should not be counted.
Right leaves must never be included in the sum.
Trees may contain negative values, so the final sum can also be negative.

Approaches

A brute-force approach would examine every node and repeatedly determine whether that node is a left leaf by searching from the root or by maintaining additional structural checks. For example, for every node we could search the tree again to identify its parent and determine whether it is a left child. This works correctly because every node is eventually checked, but it introduces unnecessary repeated traversal work.

A better solution comes from observing that tree traversal naturally gives us parent-child relationships as we recurse or iterate. While visiting a node, we already have direct access to its left and right children. This means we can immediately determine whether the left child is a leaf without any extra searching.

The key insight is that when we are standing at a node, we only need to inspect its left child:

If the left child exists and has no children, it is a left leaf and should be added to the answer.
Otherwise, continue traversing deeper into the tree.

This leads to a clean depth-first traversal where each node is processed exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly searches relationships or rescans portions of the tree
Optimal	O(n)	O(h)	Single DFS traversal that checks left leaves during traversal

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

Depth-First Search Strategy

Start a depth-first traversal from the root node.
At each node, first check whether the node has a left child. If it does, determine whether that left child is a leaf node. A leaf node is identified by having both left and right equal to None or nil.
If the left child is a leaf, add its value to the running total. We do this immediately because we have confirmed that it satisfies both conditions required by the problem.
If the left child exists but is not a leaf, recursively continue traversing into that subtree. There may still be left leaves deeper inside it.
Independently traverse the right subtree as well. Even though right children themselves are not counted, their subtrees may contain left leaves further down.
Continue this process until all nodes have been visited.
Return the accumulated sum after traversal completes.

Why it works

The algorithm works because every node in the tree is visited exactly once, and every left child is checked precisely when its parent is processed. A node is added to the sum only if it satisfies the exact definition of a left leaf: it is a left child and has no children of its own. Since the traversal explores the entire tree, no valid left leaf can be missed, and no invalid node can be incorrectly included.

Python Solution

# 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:
        def dfs(node: Optional[TreeNode]) -> int:
            if not node:
                return 0

            total = 0

            if node.left:
                is_left_leaf = (
                    node.left.left is None and
                    node.left.right is None
                )

                if is_left_leaf:
                    total += node.left.val

            total += dfs(node.left)
            total += dfs(node.right)

            return total

        return dfs(root)

The implementation uses a recursive helper function named dfs to perform a depth-first traversal of the tree.

The first condition handles the base case. If the current node is None, there is nothing to process, so the function returns 0.

For each valid node, a local variable total stores the sum contributed by the current subtree.

The code then checks whether the current node has a left child. If it does, the implementation determines whether that child is a leaf by verifying that both of its children are None.

If the left child is a leaf, its value is added to total.

After processing the immediate left child relationship, the algorithm recursively explores both the left and right subtrees. This ensures that every node in the tree is eventually examined.

Finally, the helper function returns the accumulated total for the current subtree, and the outer function returns the result starting from the root.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumOfLeftLeaves(root *TreeNode) int {
    var dfs func(node *TreeNode) int

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        total := 0

        if node.Left != nil {
            isLeftLeaf := node.Left.Left == nil &&
                node.Left.Right == nil

            if isLeftLeaf {
                total += node.Left.Val
            }
        }

        total += dfs(node.Left)
        total += dfs(node.Right)

        return total
    }

    return dfs(root)
}

The Go implementation follows the same recursive strategy as the Python solution. The main difference is Go's explicit pointer handling with nil checks instead of Python's None.

Go uses a function variable dfs to define the recursive helper closure. Integer overflow is not a concern here because the constraints are small, and the maximum possible sum easily fits within Go's standard int type.

Worked Examples

Example 1

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

Tree structure:

Traversal process:

Current Node	Left Child	Is Left Leaf?	Sum After Step
3	9	Yes	9
9	None	No	9
20	15	Yes	24
15	None	No	24
7	None	No	24

Final answer:

Example 2

Input: root = [1]

Tree structure:

Traversal process:

Current Node	Left Child	Is Left Leaf?	Sum After Step
1	None	No	0

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(h)	Recursive call stack depends on tree height

The time complexity is linear because the algorithm performs a single traversal through the tree and processes each node one time.

The space complexity comes from recursion. In the worst case, such as a completely skewed tree, the recursion depth can become O(n). In a balanced tree, the recursion depth is O(log n).

Test Cases

# Definition for testing
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):
        def dfs(node):
            if not node:
                return 0

            total = 0

            if node.left:
                is_left_leaf = (
                    node.left.left is None and
                    node.left.right is None
                )

                if is_left_leaf:
                    total += node.left.val

            total += dfs(node.left)
            total += dfs(node.right)

            return total

        return dfs(root)

solution = Solution()

# Example 1
root1 = TreeNode(
    3,
    TreeNode(9),
    TreeNode(20, TreeNode(15), TreeNode(7))
)
assert solution.sumOfLeftLeaves(root1) == 24  # standard example

# Example 2
root2 = TreeNode(1)
assert solution.sumOfLeftLeaves(root2) == 0  # single node tree

# Only right children
root3 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert solution.sumOfLeftLeaves(root3) == 0  # no left leaves exist

# Left child is not a leaf
root4 = TreeNode(1, TreeNode(2, TreeNode(3), None))
assert solution.sumOfLeftLeaves(root4) == 3  # only deepest left leaf counts

# Multiple left leaves
root5 = TreeNode(
    1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7))
)
assert solution.sumOfLeftLeaves(root5) == 10  # left leaves are 4 and 6

# Negative values
root6 = TreeNode(
    -1,
    TreeNode(-2),
    TreeNode(-3, TreeNode(-4), None)
)
assert solution.sumOfLeftLeaves(root6) == -6  # negative left leaves

# Skewed left tree
root7 = TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4))))
assert solution.sumOfLeftLeaves(root7) == 4  # only final node is leaf

# Left leaf and right leaf together
root8 = TreeNode(1, TreeNode(2), TreeNode(3))
assert solution.sumOfLeftLeaves(root8) == 2  # only left leaf counted

Test	Why
`[3,9,20,null,null,15,7]`	Validates the standard example with multiple left leaves
`[1]`	Confirms that a single-node tree returns zero
Right-skewed tree	Ensures right leaves are ignored
Left child with descendants	Verifies that non-leaf left children are not counted
Balanced tree with several leaves	Tests accumulation of multiple left leaves
Negative values	Confirms correct handling of negative sums
Left-skewed tree	Tests deep recursion and leaf detection
One left leaf and one right leaf	Verifies only left leaves contribute

Edge Cases

A single-node tree is an important edge case because the root node has no parent. Since a left leaf must be the left child of another node, the root can never qualify. A careless implementation might incorrectly count the root if it only checks whether the node is a leaf. This solution avoids that issue because it only evaluates nodes through their parent relationships.

Another tricky case occurs when a node is a left child but not a leaf. For example, in a chain like 1 -> 2 -> 3, node 2 is a left child but still has a child of its own. Only node 3 should be counted. The implementation handles this correctly by explicitly checking that both child pointers are empty before adding a value to the sum.

Trees containing only right children can also cause logical mistakes. Since no node is ever a left child in such a tree, the correct answer is always zero. The traversal still explores the entire tree, but values are added only when a left leaf condition is satisfied.

Negative node values are another subtle case. Since the problem allows values between -1000 and 1000, the sum may become negative. The implementation does not make assumptions about positivity and simply accumulates values normally, so negative left leaves are handled correctly.