Sum of Left Leaves
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses recursion to perform a depth-first traversal of the tree. The core idea is to define a function that, for any given node, calculates the sum of left leaves in the subtree rooted at that node. To identify a left leaf, we look ahead from a parent node. When at a node curr, we check its left child, curr.left. If curr.left exists and is a leaf (meaning it has no children), we've found a left leaf and add its value to our sum. We then recursively apply the same logic to the left and right subtrees to find all other left leaves.
Algorithm
- Base Case: If the current node
rootisnull, return 0. - Initialize a local variable
sumto 0. - Check if the left child of the current node is a leaf. A node
nis a leaf ifn.left == nullandn.right == null. - If
root.leftis a leaf, add its value tosum. - Recursively call the function on the left subtree (
root.left) and add the returned value tosum. - Recursively call the function on the right subtree (
root.right) and add the returned value tosum. - Return the total
sum.
Walkthrough
This approach uses recursion to perform a depth-first traversal of the tree. The core idea is to define a function that, for any given node, calculates the sum of left leaves in the subtree rooted at that node.
To identify a left leaf, we don't check the current node itself. Instead, we look ahead from a parent node. When we are at a node curr, we check its left child, curr.left. If curr.left exists and is a leaf (meaning it has no children), we've found a left leaf and add its value to our sum. We then recursively apply the same logic to the left and right subtrees to find all other left leaves.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } int sum = 0; // Check if the current node's left child is a leaf. if (root.left != null && root.left.left == null && root.left.right == null) { sum += root.left.val; } // Recursively find the sum in the left and right subtrees. sum += sumOfLeftLeaves(root.left); sum += sumOfLeftLeaves(root.right); return sum; }}Complexity
Time
O(N), where N is the number of nodes in the tree. We must visit every node to check its children.
Space
O(H), where H is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
Trade-offs
Pros
Code is concise and closely follows the recursive definition of a tree.
Easy to understand and implement.
Cons
Can lead to a
StackOverflowErrorfor very deep trees.Function call overhead can be slightly less performant than an iterative solution.
An alternative iterative approach is to use Breadth-First Search (BFS), which explores the tree level by level. This method uses a queue instead of a stack. While the time complexity is the same as DFS, the space complexity depends on the maximum width of the tree, which can be more or less efficient than DFS depending on the tree's structure. The logic remains similar: we traverse the tree, and for each node we visit, we check if its left child is a leaf.
Algorithm
- If
rootisnull, return 0. - Initialize
totalSum = 0. - Create a
Queue<TreeNode>and offer theroot. - While the queue is not empty:
- Poll a node
nodefrom the queue. - Check if
node.leftis a leaf. If it is, addnode.left.valtototalSum. - If
node.leftis notnull, offer it to the queue. - If
node.rightis notnull, offer it to the queue.
- Poll a node
- Return
totalSum.
Walkthrough
An alternative iterative approach is to use Breadth-First Search (BFS), which explores the tree level by level. This method uses a queue instead of a stack. While the time complexity is the same as DFS, the space complexity depends on the maximum width of the tree, which can be more or less efficient than DFS depending on the tree's structure.
The logic remains similar: we traverse the tree, and for each node we visit, we check if its left child is a leaf. If so, we add its value to our running total.
import java.util.Queue;import java.util.LinkedList; class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } int totalSum = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); // Check if the left child is a leaf if (node.left != null && node.left.left == null && node.left.right == null) { totalSum += node.left.val; } // Add children to the queue for the next level if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } return totalSum; }}Complexity
Time
O(N), as each node is enqueued and dequeued exactly once.
Space
O(W), where W is the maximum width of the tree. In the worst case of a complete binary tree, the last level can contain up to N/2 nodes, leading to O(N) space complexity.
Trade-offs
Pros
Avoids recursion, thus preventing
StackOverflowError.Can be more space-efficient than DFS for very deep and narrow (skewed) trees.
Cons
Can use significantly more memory than DFS for wide, balanced trees.
The code is slightly more verbose than the recursive version.
To avoid the potential for stack overflow in very deep trees and the overhead of recursive function calls, we can implement the DFS traversal iteratively using an explicit stack. This approach mirrors the logic of the recursive solution but manages the traversal manually. We start by pushing the root node onto a stack. Then, we loop as long as the stack is not empty. In each iteration, we pop a node, check if its left child is a leaf, and then push its non-null children onto the stack for future processing.
Algorithm
- If
rootisnull, return 0. - Initialize
totalSum = 0. - Create a
Stack<TreeNode>and push theroot. - While the stack is not empty:
- Pop a node
nodefrom the stack. - Check if
node.leftis a leaf. If it is, addnode.left.valtototalSum. - If
node.rightis notnull, push it onto the stack. - If
node.leftis notnull, push it onto the stack.
- Pop a node
- Return
totalSum.
Walkthrough
To avoid the potential for stack overflow in very deep trees and the overhead of recursive function calls, we can implement the DFS traversal iteratively using an explicit stack. This approach mirrors the logic of the recursive solution but manages the traversal manually.
We start by pushing the root node onto a stack. Then, we loop as long as the stack is not empty. In each iteration, we pop a node, check if its left child is a leaf (and add its value to the sum if so), and then push its non-null children (right then left, to process the left subtree first) onto the stack for future processing.
import java.util.Stack; class Solution { public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } int totalSum = 0; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); // Check if the left child is a leaf if (node.left != null && node.left.left == null && node.left.right == null) { totalSum += node.left.val; } // Push children onto the stack for traversal if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return totalSum; }}Complexity
Time
O(N), as each node is pushed onto and popped from the stack exactly once.
Space
O(H), where H is the height of the tree. This space is used by the explicit stack. In the worst case of a skewed tree, H can be N, leading to O(N) space. For a balanced tree, it's O(log N).
Trade-offs
Pros
Avoids recursion and the risk of
StackOverflowError.Generally more space-efficient than BFS for typical (balanced) trees.
Directly translates the recursive logic into an iterative form.
Cons
Can use O(N) space for a skewed tree, which is its worst-case.
Slightly more complex to write than the recursive approach.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int sumOfLeftLeaves ( TreeNode root ) { if ( root == null ) { return 0 ; } int res = 0 ; if ( root . left != null && root . left . left == null && root . left . right == null ) { res += root . left . val ; } res += sumOfLeftLeaves ( root . left ); res += sumOfLeftLeaves ( root . right ); return res ; } }/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int sumOfLeftLeaves ( TreeNode * root ) { if ( ! root ) { return 0 ; } int ans = sumOfLeftLeaves ( root -> right ); if ( root -> left ) { if ( ! root -> left -> left && ! root -> left -> right ) { ans += root -> left -> val ; } else { ans += sumOfLeftLeaves ( root -> left ); } } return ans ; } };# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution : def sumOfLeftLeaves ( self , root : TreeNode ) -> int : if root is None : return 0 res = 0 if root . left and root . left . left is None and root . left . right is None : res += root . left . val res += self . sumOfLeftLeaves ( root . left ) res += self . sumOfLeftLeaves ( root . right ) return resVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.