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:
[1, 1000].-1000 <= Node.val <= 1000In #404 Sum of Left Leaves, the goal is to traverse a binary tree and add the values of nodes that are left leaves. A left leaf is a node that is the left child of its parent and has no children of its own. The key idea is to visit each node and check whether its left child satisfies the leaf condition.
A common strategy is using Depth-First Search (DFS). While traversing the tree recursively, check if the current node has a left child and whether that child is a leaf (both children are null). If so, add its value to the sum. Otherwise, continue exploring the subtree. Alternatively, a Breadth-First Search (BFS) approach with a queue can iterate level by level while performing the same check.
Both approaches ensure that every node is visited exactly once, making them efficient for this problem while keeping the logic simple and readable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (Recursive) | O(n) | O(h) |
| Breadth-First Search (Queue) | O(n) | O(n) |
Kevin Naughton Jr.
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.
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.
1#include <iostream>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int dfs(TreeNode* node, bool isLeft) {
14 if (!node) return 0;
if (!node->left && !node->right && isLeft) return node->val;
return dfs(node->left, true) + dfs(node->right, false);
}
int sumOfLeftLeaves(TreeNode* root) {
return dfs(root, false);
}
};In C++, we define a class Solution and use a similar recursive approach. The dfs helper function handles the logic of summing left leaf nodes by traversing the tree recursively.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of binary tree traversal problems like Sum of Left Leaves are commonly asked in FAANG-style interviews. They test understanding of tree structures, recursion, and traversal strategies such as DFS and BFS.
A left leaf is a node that is the left child of its parent and has no left or right children. During traversal, you simply check if the current node's left child exists and both of its children are null.
The optimal approach is to traverse the binary tree using DFS or BFS and check whether each node's left child is a leaf. If the left child has no children, its value is added to the total. This ensures every node is processed once, giving O(n) time complexity.
Binary tree traversal techniques work best for this problem. DFS typically uses recursion and the call stack, while BFS uses a queue to process nodes level by level.
The iterative approach leverages a stack to simulate recursion iteratively in Python. Nodes are pushed onto a stack with information on whether they are left children. Left leaf nodes values are accumulated forming the result.