Kth Largest Sum in a Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree. Each level of the tree has a sum formed by adding the values of all nodes on that level. The task is to compute every level sum and return the kth largest among them. If the tree has fewer than k levels, return -1.

Approach 1: Breadth-First Search with Min-Heap (O(n log k) time, O(w + k) space)

This approach processes the tree level by level using Breadth-First Search. Use a queue to iterate through each level and compute the sum of node values at that level. Instead of storing every level sum, maintain a min-heap of size k. After computing a level sum, push it into the heap; if the heap size exceeds k, remove the smallest element. The heap always stores the k largest level sums seen so far, and the root of the heap is the kth largest. This reduces sorting overhead and avoids storing all sums when the tree has many levels.

The time complexity is O(n log k) because every node is visited once and each heap operation costs log k. Space complexity is O(w + k), where w is the maximum tree width due to the BFS queue. This approach is typically the most efficient when k is much smaller than the number of levels.

Approach 2: Depth-First Search with Level Tracking (O(n + L log L) time, O(L) space)

This approach uses tree traversal with DFS while tracking the current depth. Maintain an array (or hash map) where the index represents the level and the value stores the cumulative sum of nodes at that level. During recursion, add the node value to the corresponding level entry. If the level does not exist yet, append a new entry.

After the traversal completes, the array contains all level sums. Sort the array in descending order using a standard sorting algorithm and return the element at index k - 1. If the array length is smaller than k, return -1. DFS visits each node exactly once, giving O(n) traversal time. Sorting the L level sums adds O(L log L), where L is the number of levels.

This method is straightforward and easy to implement. It works well when the number of levels is relatively small and when you prefer recursive traversal over queue-based iteration.

Recommended for interviews: BFS with a min-heap is usually the expected optimal solution. It demonstrates strong understanding of binary tree traversal and heap optimization. A brute-force style solution that collects all sums and sorts them shows basic problem understanding, but maintaining a heap of size k proves you can reduce unnecessary work and control memory usage.