Sum of Left Leaves
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.
A node cannot determine on its own whether it is a "left leaf." A leaf node holds no reference to its parent, so it has no way to know whether it is a left child or a right child. That information lives in the parent. The fix is to check from the parent's side: when we visit a node, look at its left child. If that left child has no children of its own, it is a left leaf, so add its value to the sum. We never add the current node's value, only the value of a qualifying left child.
The alternative is to pass a flag like "am I a left child?" down through the recursion. Both work, but checking from the parent avoids carrying that extra state.
Key Constraints:
Number of nodes in [1, 1000]--> Any standard traversal runs in O(n), which is optimal because every node must be visited at least once to know whether it is a left leaf.-1000 <= Node.val <= 1000--> Values can be negative, so a left leaf can lower the total. Negative left leaves still count and cannot be skipped.At least 1 node--> The root always exists. A single-node tree returns 0, since the root is not the left child of any parent.
Approach 1: Recursive DFS
Intuition
A binary tree is defined in terms of itself, so recursion maps onto its structure directly. At each node we evaluate one condition: is the left child a leaf?
A left child is a leaf when it exists and both left.left and left.right are null. When that holds, we add its value. Then we recurse into both subtrees to collect any left leaves deeper in the tree.
The sum only ever counts the value of a qualifying left child, never the current node. Because the check always looks one level down, no "isLeft" flag has to travel through 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 optimal in time, but it relies on the call stack, which grows with the tree's height. A deeply skewed tree can exhaust the stack. An iterative traversal removes that risk by managing its own data structure on the heap.
Approach 2: Iterative BFS
Intuition
A queue lets us traverse the tree level by level without recursion. The left-leaf check is identical to the recursive version: for each node we dequeue, if its left child has no children, add that child's value to the total.
BFS has a different space profile from DFS. Its memory use scales with the tree's maximum width rather than its height. On a skewed tree, where recursion risks a stack overflow, each level holds a single node, so the queue never exceeds O(1) entries.
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).