Kth Largest Sum in a Binary Tree — BFS Level Sums with Heap Selection
Sanjeev SharmaAdvertisement
Problem Statement
You are given the root of a binary tree and a positive integer k. Return the kth largest sum among all level sums of the tree. If the number of levels is less than k, return -1.
The level sum of a level l is the sum of values of all nodes at level l. The root is at level 1.
Constraints:
- The number of nodes in the tree is
n, where2 <= n <= 10^5. 1 <= Node.val <= 10^61 <= k <= n
Examples:
Example 1:
Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Tree:
5
/ \
8 9
/ \ / \
2 1 3 7
/ \
4 6
Level sums: [5, 17, 13, 10]
Output: 13 (2nd largest)
Example 2:
Input: root = [1,2,null,3], k = 1
Level sums: [1, 2, 3]
Output: 3 (1st largest)Why This Problem Matters
Kth Largest Sum in a Binary Tree is a medium problem that elegantly combines two fundamental patterns: BFS level-order traversal and kth largest selection with a min-heap. Amazon and Google use it to verify that candidates can compositely apply multiple algorithmic tools rather than treating each in isolation.
The problem tests the BFS level-order sum computation (a common interview building block) and then asks you to efficiently extract the kth largest from the resulting list. The heap-based kth largest selection (maintaining a size-k min-heap) is a canonical pattern that appears in Top K Frequent Elements, K Closest Points to Origin, and many other problems.
A subtle but important interview point: should you sort the level sums or use a min-heap of size k? For small trees, sorting is fine. But for a tree with 10^5 nodes and potentially 10^4 levels, maintaining a size-k heap gives O(L log k) instead of O(L log L) where L = number of levels. The interviewer may ask you to justify this choice.
This problem is also notable because it tests edge cases: what if k exceeds the number of levels? What if multiple levels have the same sum? What if the tree is a single path (linear depth)?
The Core Insight
The algorithm has two clean phases:
Phase 1 — BFS level sum computation: Use standard BFS (queue-based level-order traversal). For each level, sum all node values. Collect all level sums into a list.
Phase 2 — Kth largest selection: Two approaches:
- Sort descending, return index k-1. Simple and readable. O(L log L).
- Min-heap of size k. Maintain a min-heap; push each level sum and pop if size exceeds k. The heap top is the kth largest. O(L log k).
For this problem's constraints (at most 10^5 nodes, so at most 10^5 levels but realistically O(log n) for balanced trees), both approaches are efficient. The min-heap approach is preferred as it uses less memory for large inputs with large L and small k.
Key insight for the heap approach: A min-heap of size k always contains the k largest elements seen so far. Its top (minimum of those k) is the kth largest.
Visual Dry Run
Tree:
5
/ \
8 9
/ \ / \
2 1 3 7
/ \
4 6
BFS Traversal:
Level 1: nodes=[5]. Sum = 5.
Level 2: nodes=[8,9]. Sum = 17.
Level 3: nodes=[2,1,3,7]. Sum = 13.
Level 4: nodes=[4,6]. Sum = 10.
level_sums = [5, 17, 13, 10]
kth largest, k=2:
Method 1: sort descending → [17, 13, 10, 5]. Return index 1 = 13. ✓
Method 2 (min-heap, size k=2):
Push 5: heap=[5]. size=1 ≤ 2.
Push 17: heap=[5,17]. size=2 ≤ 2.
Push 13: heap=[5,13,17]? No: push 13, size=3 > 2, pop min=5. heap=[13,17].
Push 10: push 10, size=3 > 2, pop min=10. heap=[13,17].
Return heap top = 13. ✓Solution (Optimal)
from collections import deque
import heapq
def kthLargestLevelSum(root, k):
if not root:
return -1
# Phase 1: BFS to compute level sums
level_sums = []
queue = deque([root])
while queue:
level_sum = 0
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level_sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
level_sums.append(level_sum)
# Phase 2: Find kth largest using min-heap of size k
if k > len(level_sums):
return -1
min_heap = []
for s in level_sums:
heapq.heappush(min_heap, s)
if len(min_heap) > k:
heapq.heappop(min_heap) # remove smallest, keeping top-k
return min_heap[0] # smallest of top-k = kth largestfunction kthLargestLevelSum(root, k) {
if (!root) return -1;
// Phase 1: BFS level-order sum
const levelSums = [];
let queue = [root];
while (queue.length) {
let levelSum = 0;
const nextQueue = [];
for (const node of queue) {
levelSum += node.val;
if (node.left) nextQueue.push(node.left);
if (node.right) nextQueue.push(node.right);
}
levelSums.push(levelSum);
queue = nextQueue;
}
// Phase 2: Kth largest
if (k > levelSums.length) return -1;
// Sort descending and return index k-1
// For large inputs, use a min-heap of size k (see Python)
levelSums.sort((a, b) => b - a);
return levelSums[k - 1];
}Complexity Analysis:
- BFS: O(n) — visits each node exactly once
- Kth largest (sort): O(L log L) where L = number of levels
- Kth largest (heap): O(L log k)
- Overall: O(n + L log k) = O(n) since L ≤ n and log k ≤ log n
- Space: O(w + k) where w = maximum level width (for BFS queue) and k for the heap
Common Mistakes
- Returning -1 when k equals the number of levels. If there are exactly k levels, the kth largest is the smallest level sum — not -1. Return -1 only if k is strictly greater than the number of levels.
- Confusing level index with k. Level sums are 1-indexed in the problem description, but the array is 0-indexed. After sorting, the kth largest is at index
k-1. - Using DFS instead of BFS. DFS can compute level sums but requires careful tracking of the current depth. BFS is cleaner and more natural.
- Not checking if root is null. An empty tree should return -1 immediately.
- Integer overflow. Level sums can be up to 10^5 nodes × 10^6 per node = 10^11, which overflows 32-bit integers. Use 64-bit (
longin Java,BigIntin JavaScript if needed, or justintin Python which handles arbitrary precision).
Follow-up Questions
- What is the expected level sum for a balanced binary tree with n nodes and uniform values?
- Find the level with the minimum sum. How does the algorithm change?
- What if you want the average (mean) of all level sums? Divide total by number of levels after BFS.
- Compute all level sums in sorted order. How would you extend the solution?
- What is the maximum possible number of levels in a tree with n nodes? When does this occur?
- Can you compute level sums during a single DFS pass without extra memory for the queue?
Related Problems
- LeetCode 637 — Average of Levels in Binary Tree: BFS level sums divided by level size; same BFS structure.
- LeetCode 515 — Find Largest Value in Each Tree Row: BFS and track max per level; same traversal.
- LeetCode 1161 — Maximum Level Sum of a Binary Tree: Find the level with maximum sum; simpler variant.
- LeetCode 2583 — Kth Largest Sum in a Binary Tree: This exact problem.
- LeetCode 215 — Kth Largest Element in an Array: Kth largest selection; core sub-problem.
- LeetCode 347 — Top K Frequent Elements: Top k selection with heap; same min-heap of size k pattern.
Key Takeaways
- BFS level-order traversal naturally computes level sums: process all nodes at one level before moving to the next.
- A min-heap of size k gives the kth largest in O(L log k) where L is the number of levels — better than O(L log L) sort for large L with small k.
- The heap invariant: after processing all L levels, the heap contains the k largest level sums, and its minimum (the top) is the kth largest.
- Return -1 only when k is strictly greater than the number of levels, not when k equals the number of levels.
- Integer overflow is a real risk: level sums can reach 10^5 nodes times 10^6 per node = 10^11, requiring 64-bit arithmetic in Java.
- BFS uses a queue; the queue width at any level equals the number of nodes at that level — space is O(max_width), which can be O(n) for a perfectly balanced tree.
- Amazon and Google use this problem as a two-phase composition test: BFS mastery plus kth-largest heap selection in one problem.
Advertisement
