Sum of Left Leaves - Solution & Explanation
Problem Statement
Given the root of a binary tree, return the sum of all left leaves.
A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: 24 Explanation: There are two left leaves in the binary tree, with values 9 and 15 respectively.
Example 2:
Input: root = [1] Output: 0
Constraints:
- The number of nodes in the tree is in the range
[1, 1000]. -1000 <= Node.val <= 1000
Approach Overview
Problem Overview: You are given the root of a binary tree and need to compute the sum of all left leaves. A left leaf is a node that is both a left child of its parent and has no children of its own. The task is essentially a traversal problem: visit each node and check whether its left child qualifies as a leaf.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
This approach performs a standard recursive traversal of the binary tree. At each node, check whether the left child exists and whether that left child is a leaf (both left and right pointers are null). If so, add its value to the running sum. Otherwise, continue the recursion on both left and right subtrees. The key insight is that you don't need to process every leaf—only those reached through a left edge. Each node is visited once, giving O(n) time complexity where n is the number of nodes. The recursion stack grows up to the height of the tree, which results in O(h) auxiliary space.
This solution is concise and mirrors the natural structure of the tree. Most engineers prefer this version when solving problems involving recursive tree traversal because the logic stays close to the definition of the structure itself.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
The iterative version replaces recursion with an explicit stack to simulate depth-first search. Push the root node onto a stack and repeatedly pop nodes for processing. For each node, check whether its left child exists and whether it is a leaf. If it is, add its value to the total. Otherwise push the left child to the stack so its subtree can be explored. The right child is also pushed when present so the traversal eventually covers the entire tree.
This method still visits every node exactly once, resulting in O(n) time complexity. The stack stores nodes along the current traversal path, so the space usage remains O(h), where h is the height of the tree. Iterative DFS is useful when recursion depth might be large or when you want more explicit control over traversal order in a tree structure.
Recommended for interviews: Recursive DFS is the solution most interviewers expect. It clearly demonstrates your understanding of tree traversal and keeps the implementation short and readable. Mentioning the iterative stack-based DFS shows deeper understanding and awareness of recursion limits. Both approaches achieve the optimal O(n) time complexity since every node must be inspected to determine whether it forms a left leaf.
Approach 1: Recursive Depth-First Search (DFS)
This approach involves using recursive DFS to traverse the tree. At each node, determine if it is a left leaf. If it is, add its value to the sum and recursively continue to search for more left leaves in the subtree.
We define a helper function dfs which takes a node and a boolean indicating whether it is a left child. If the node is a leaf and is a left child, we add its value to the sum. Otherwise, recurse into the left and right subtrees.
Complexity
The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.
Approach 2: Iterative Depth-First Search
This approach applies iterative DFS using a stack. By exploring each node iteratively, it checks if a node qualifies as a left leaf and accumulates its value to the sum. It manages to mimic a recursive pattern iteratively.
This C solution uses a custom stack to perform an iterative DFS. It pushes nodes onto the stack and processes them. If deemed a left leaf, its value contributes to the sum. By simulating recursion iteratively, this approach eliminates associated stack memory drawbacks.
Complexity
The time complexity is O(n) for navigating each tree node once. Space complexity is O(n) due to maintaining a stack proportional to the number of nodes.
Approach 3: Recursion
First, we check if root is null. If it is, we return 0.
Otherwise, we recursively call the sumOfLeftLeaves function to calculate the sum of all left leaves in root's right subtree, and assign the result to the answer variable ans. Then we check if root's left child exists. If it does, we check if it is a leaf node. If it is a leaf node, we add its value to the answer variable ans. Otherwise, we recursively call the sumOfLeftLeaves function to calculate the sum of all left leaves in root's left subtree, and add the result to the answer variable ans.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.
Approach 4: Stack
We can also convert the recursion in Solution 1 to iteration, using a stack to simulate the recursion process.
Similar to Solution 1, we first check if root is null. If it is, we return 0.
Otherwise, we initialize the answer variable ans to 0, and then initialize a stack stk and add root to the stack.
While the stack is not empty, we pop the top element root from the stack. If root's left child exists, we check if it is a leaf node. If it is a leaf node, we add its value to the answer variable ans. Otherwise, we add its left child to the stack. Then we check if root's right child exists. If it does, we add it to the stack.
Finally, we return the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack. |
| Iterative Depth-First Search | The time complexity is O(n) for navigating each tree node once. Space complexity is O(n) due to maintaining a stack proportional to the number of nodes. |
| Recursion | — |
| Stack | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(n) | O(h) | Best general solution for binary tree traversal. Clean and easy to implement in interviews. |
| Iterative Depth-First Search (Stack) | O(n) | O(h) | Useful when avoiding recursion depth limits or when explicit control of traversal stack is preferred. |
Video Solution
Sum of Left Leaves • Kevin Naughton Jr. • 25,825 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sum of Left Leaves easy or hard?
Sum of Left Leaves Python/Java solution
How to solve Sum of Left Leaves in O(n)?
What is the best approach for Sum of Left Leaves?
Is Sum of Left Leaves asked at Google/Amazon/Meta?
What data structure is used in Sum of Left Leaves?
What is the time complexity of Sum of Left Leaves?
Ready to solve this problem?
Practice Sum of Left Leaves with our built-in code editor and test cases.
Practice on FleetCode