Deepest Leaves Sum — Solution in Python, Java & C++
Deepest Leaves Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Deepest Leaves Sum is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return the sum of the values of the leaves that lie on its deepest level.
Example 1
Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15
Explanation: The deepest level holds 7 and 8, so the answer is 15.
Example 2
Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19
Explanation: The deepest level holds 9, 1, 4 and 5, which add up to 19.
Example 3
Input: root = [4]
Output: 4
Explanation: The root is the only (and deepest) leaf.
Constraints
1 <= number of nodes <= 10^41 <= Node.val <= 100
Hints for Deepest Leaves Sum
Hint 1
Every node on the deepest level is a leaf, so the answer is simply the sum of the last level.
Hint 2
Walk the tree level by level and remember only the sum of the level you just finished.
Hint 3
When a level produces no children, the sum you are holding is the answer.
How to solve Deepest Leaves Sum
The deepest level consists only of leaves, so a level-by-level walk that keeps the sum of the most recent level ends holding the answer.
Approach
- Start with the level containing only the root.
- For each level, add up its values and collect its children as the next level.
- When the next level is empty, return the sum of the current one.
Why it works
A node on the deepest level cannot have children (they would be deeper), so all its nodes are leaves, and every leaf on that level is one of its nodes. The walk ends exactly after processing that level.
Complexity
- Time —
O(n) - Space —
O(w), w the widest level
Pitfalls
- Summing every leaf instead of only the deepest ones.
- A depth-first version must reset the running sum whenever it meets a deeper leaf than any seen so far.
Reference solution
Python
from typing import Optional
def deepestLeavesSum(root: Optional[TreeNode]) -> int:
level = [root]
while True:
total = 0
nxt = []
for node in level:
total += node.val
if node.left:
nxt.append(node.left)
if node.right:
nxt.append(node.right)
if not nxt:
return total
level = nxtJava
public static int deepestLeavesSum(TreeNode root) {
List<TreeNode> level = new ArrayList<>();
level.add(root);
while (true) {
int total = 0;
List<TreeNode> next = new ArrayList<>();
for (TreeNode node : level) {
total += node.val;
if (node.left != null) next.add(node.left);
if (node.right != null) next.add(node.right);
}
if (next.isEmpty()) return total;
level = next;
}
}C++
int deepestLeavesSum(TreeNode* root) {
vector<TreeNode*> level{root};
while (true) {
int total = 0;
vector<TreeNode*> next;
for (TreeNode* node : level) {
total += node->val;
if (node->left) next.push_back(node->left);
if (node->right) next.push_back(node->right);
}
if (next.empty()) return total;
level.swap(next);
}
}JavaScript
var deepestLeavesSum = function(root) {
var level = [root];
for (;;) {
var total = 0, next = [];
for (var i = 0; i < level.length; i++) {
var node = level[i];
total += node.val;
if (node.left !== null) next.push(node.left);
if (node.right !== null) next.push(node.right);
}
if (next.length === 0) return total;
level = next;
}
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)