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 <= 100Problem Overview: Given the root of a binary tree, compute the sum of all node values located at the deepest level. The task is to identify the maximum depth of the tree and add the values of every node that appears at that level.
Approach 1: Level Order Traversal (BFS) (Time: O(n), Space: O(n))
This approach performs a breadth-first traversal using a queue. Process the tree level by level. For each level, iterate through all nodes currently in the queue and compute their sum while pushing their children into the queue for the next level. The key observation: the final level processed in BFS is the deepest level. Keep overwriting the level sum during traversal, and once the queue becomes empty, the last computed sum represents the sum of the deepest leaves. This method works naturally with level-based problems and is often the most intuitive solution when the task explicitly depends on tree depth. BFS uses a queue and may hold up to O(n) nodes in the worst case (for a wide tree). Learn more about Breadth-First Search and how it applies to Binary Tree problems.
Approach 2: Depth-First Search (DFS) with Depth Tracking (Time: O(n), Space: O(h) to O(n))
DFS explores the tree recursively while tracking the current depth. Maintain two variables: maxDepth and sum. When visiting a node, compare its depth with maxDepth. If the depth exceeds maxDepth, update maxDepth and reset the sum to the node's value. If the depth equals maxDepth, add the node value to the sum. Continue exploring both left and right subtrees. By the time traversal completes, the sum contains values of all nodes at the deepest level. The recursion stack uses O(h) space for balanced trees and up to O(n) in the worst-case skewed tree. This method is flexible when you need depth information during traversal and integrates naturally with recursive Depth-First Search patterns.
Recommended for interviews: Level Order Traversal (BFS) is usually the expected solution because the problem directly refers to the deepest level, which BFS exposes naturally by processing nodes layer by layer. DFS with depth tracking demonstrates stronger understanding of recursive tree traversal and state management. Showing both approaches during discussion signals solid grasp of tree traversal strategies.
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.
We initialize a queue and push the root node into it. Then, we iterate while the queue is not empty, processing all nodes at the current level and updating the sum. If there are nodes left to explore after processing a level, we reset the sum for the next 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.
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.
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.
Time Complexity: O(n)
Space Complexity: O(h), where h is the height of the tree due to recursion stack.
We can use breadth-first search (BFS) to traverse the binary tree level by level, and calculate the sum of the node values at each level. After completing the traversal, return the sum of the node values at the last level.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.
We can use depth-first search (DFS) to recursively traverse the binary tree while keeping track of the current node's depth, the maximum depth, and the sum of the deepest leaf nodes. When visiting the current node, if the current node's depth equals the maximum depth, add the current node's value to the sum of the deepest leaf nodes. If the current node's depth is greater than the maximum depth, update the maximum depth to the current node's depth and update the sum of the deepest leaf nodes to the current node's value.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the tree.
| Approach | Complexity |
|---|---|
| Level Order Traversal (BFS) | Time Complexity: O(n), where n is the number of nodes in the binary tree. |
| Depth-First Search (DFS) | Time Complexity: O(n) |
| BFS | — |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal (BFS) | O(n) | O(n) | Best when solving level-based tree problems where you need values from a specific depth. |
| Depth-First Search (DFS) with Depth Tracking | O(n) | O(h) to O(n) | Useful when recursion is preferred or when depth information must be tracked during traversal. |
LeetCode 1302. Deepest Leaves Sum (Algorithm Explained) • Nick White • 13,115 views views
Watch 9 more video solutions →Practice Deepest Leaves Sum with our built-in code editor and test cases.
Practice on FleetCode