root of a binary tree, return the sum of values of its deepest leaves.
Example 1:
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8] Output: 15
Example 2:
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5] Output: 19
Constraints:
[1, 104].1 <= Node.val <= 100The goal of Deepest Leaves Sum is to compute the total value of nodes located at the deepest level of a binary tree. A common way to approach this is by understanding how to traverse the tree level by level or track the depth during traversal.
One intuitive method uses Breadth-First Search (BFS) with a queue. By performing a level-order traversal, you process nodes level by level and keep updating the sum for the current level. When the traversal finishes, the last processed level represents the deepest leaves.
Another efficient technique uses Depth-First Search (DFS). During recursion, track the current depth and maintain the maximum depth seen so far. Whenever a node at a deeper level is found, reset the sum; if the depth matches the maximum, add its value to the sum.
Both approaches visit each node once, making them efficient for large trees. BFS is often easier to visualize for level-based problems, while DFS provides a compact recursive solution.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (Level Order) | O(n) | O(n) |
| Depth-First Search (Depth Tracking) | O(n) | O(h) |
Nick White
Use these hints if you're stuck. Try solving on your own first.
Traverse the tree to find the max depth.
Traverse the tree again to compute the sum required.
This approach leverages a Breadth-First Search (BFS) traversal method using a queue to explore each level of the binary tree fully before moving on to the next level. By summing values at each level during the traversal, we can determine the sum of the deepest leaves by replacing the sum at every level.
Time Complexity: O(n), where n is the number of nodes in the binary tree.
Space Complexity: O(n), for storing nodes in the queue.
1#include <iostream>
2#include <queue>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11int deepestLeavesSum(TreeNode* root) {
12 if (!root) return 0;
13 std::queue<TreeNode*> q;
14 q.push(root);
15 int sum = 0;
16
17 while (!q.empty()) {
18 int size = q.size();
19 sum = 0;
20 for (int i = 0; i < size; ++i) {
21 TreeNode* node = q.front();
22 q.pop();
23 sum += node->val;
24 if (node->left) q.push(node->left);
25 if (node->right) q.push(node->right);
26 }
27 }
28
29 return sum;
30}The solution uses a queue to perform a level order traversal. At each level, it clears the previous sum and computes the new sum for the current level. After the last level is processed, the sum contains the sum of the deepest leaves.
This alternative approach uses Depth-First Search (DFS) to traverse the binary tree and keeps track of the maximum depth and accumulated sum of the node values at that depth.
Time Complexity: O(n)
Space Complexity: O(h), where h is the height of the tree due to recursion stack.
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, DFS is a popular solution. By recursively traversing the tree and keeping track of the current depth and deepest level encountered, you can update the sum whenever nodes appear at the maximum depth.
Yes, variations of binary tree traversal problems like Deepest Leaves Sum are common in technical interviews at large tech companies. They test understanding of tree traversal strategies such as BFS and DFS.
A queue is commonly used for the BFS approach to process the tree level by level. For the DFS method, recursion with variables tracking maximum depth and cumulative sum works effectively.
The optimal approaches use either Breadth-First Search (level order traversal) or Depth-First Search with depth tracking. Both methods visit every node once and compute the sum of nodes at the deepest level efficiently.
In this C implementation, we perform a DFS, updating the max depth and sum at that depth. When equal to max depth, accumulate the node values.