Sum of Left Leaves
Last Updated: March 29, 2026
Understanding the Problem
We're given a binary tree and need to find the sum of values of all "left leaves." Two conditions must both be true for a node to count: it must be a leaf (no left or right child), and it must be the left child of its parent.
The tricky part here is that we can't determine if a node is a "left leaf" just by looking at the node itself. A leaf node doesn't know whether it's a left child or a right child. We need information from the parent. So the key observation is this: when we visit a node, we should check if its left child is a leaf. If it is, we add that child's value to our sum. We don't add the current node's value, we add its left child's value when that child has no children of its own.
This parent-checks-child approach is simpler and cleaner than passing a flag like "am I a left child?" through recursion, though both work.
Key Constraints:
Number of nodes in [1, 1000]--> The tree is small. Any standard traversal gives us O(n), which is optimal since we must visit every node.-1000 <= Node.val <= 1000--> Values can be negative, so a left leaf might subtract from the total. We can't skip negative values.At least 1 node--> The root always exists, but it might be a single node with no children (answer would be 0 since the root itself is not a "left" child of anything).
Approach 1: Recursive DFS
Intuition
The most natural way to process a binary tree is with recursion. We visit each node, and at each node, we ask one simple question: is my left child a leaf?
A left child is a leaf if it exists but has no children of its own (both left.left and left.right are null). If that's the case, we take its value. Then we recurse into both the left subtree and the right subtree to find any other left leaves deeper in the tree.
Notice we don't add the current node's value. We're always looking one level down, checking whether the left child qualifies. This avoids the need for any "isLeft" flag in the recursion.
Algorithm
- If the current node is
null, return 0. - Initialize
sum = 0. - Check if the left child exists and is a leaf (no left or right child). If so, add
left.valtosum. - If the left child exists but is not a leaf, recurse into the left subtree and add the result to
sum. - Recurse into the right subtree and add the result to
sum. - Return
sum.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node in the tree exactly once. At each node, we do O(1) work checking if the left child is a leaf.
- Space Complexity: O(h), where h is the height of the tree. The recursion stack can go as deep as the tree height. For a skewed tree, h = n. For a balanced tree, h = log n.
The recursive approach is clean and optimal in time, but it uses the call stack. For very deep trees, this could cause a stack overflow. Can we solve it iteratively instead?
Approach 2: Iterative BFS
Intuition
Instead of recursion, we can use a queue to traverse the tree level by level. The core logic stays exactly the same: for each node we process, check if its left child is a leaf. If so, add the left child's value to our running total.
BFS has a different space profile than DFS. Instead of space proportional to the tree's height, it uses space proportional to the tree's maximum width. For skewed trees (where recursion is most dangerous), BFS uses only O(1) space since each level has just one node.
Algorithm
- If
rootisnull, return 0. - Create a queue and add
rootto it. - Initialize
sum = 0. - While the queue is not empty:
- Dequeue a node.
- If its left child exists and is a leaf, add
left.valtosum. - If its left child exists and is not a leaf, enqueue the left child.
- If its right child exists, enqueue the right child.
- Return
sum.
Example Walkthrough
Code
- Time Complexity: O(n). We process every node in the tree exactly once. Each node involves O(1) work.
- Space Complexity: O(w), where w is the maximum width of the tree. The queue holds at most one level at a time. For a balanced tree, the widest level has about n/2 nodes. For a skewed tree, each level has one node, so space is O(1).