LeetCode [2583] - Kth Largest Sum in a Binary Tree

Problem Overview:

When dealing with binary trees, one of the most common operations is traversing nodes either in a depth-first or breadth-first manner. A more advanced challenge is to find the k-th largest sum of node values at each level of the tree.

For example, consider the following binary tree:

        5
       / \
      3   8
     / \   \
    1   4   9        

In this tree, the sums for each level are:

• Level 1 sum: 5
• Level 2 sum: 3 + 8 = 11
• Level 3 sum: 1 + 4 + 9 = 14

Given k = 2, the second largest level sum is 11.

Naive Approach (Less Optimized Solution):

In the first approach, we use Breadth-First Search (BFS) to traverse the tree level-by-level. At each level, we calculate the sum of the node values and store the result in a max-heap (priority queue). Finally, we extract the k-th largest sum by popping the top k - 1 elements from the heap.

Step-by-Step Explanation:

1. Perform BFS to traverse the tree level-by-level.
2. For each level, compute the sum of the node values.
3. Insert the sum into a max-heap.
4. After processing all levels, extract the k-th largest sum from the heap.

long long kthLargestLevelSum(TreeNode* root, int k) {
    priority_queue<long> pq;
    queue<TreeNode*> queue;
    queue.push(root);
    
    while (!queue.empty()) {
        long sum = 0;
        long size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode* item = queue.front();
            sum += item->val;
            queue.pop();
            
            if (item->left) queue.push(item->left);
            if (item->right) queue.push(item->right);
        }
        pq.push(sum);
    }
    
    if (pq.size() < k) return -1;
    for (int i = 0; i < k - 1; i++) pq.pop();
    
    return pq.top();
}        

Time and Space Complexity (Naive Solution):

• Time Complexity: O(n log n), where n is the number of levels in the tree. Each insertion into the max-heap takes O(log n), and this operation is performed for each level.
• Space Complexity: O(n) because all the level sums are stored in the max-heap.

Optimized Approach:

In the optimized solution, we still use BFS to traverse the tree, but instead of maintaining a max-heap, we use a min-heap of size k to store only the k largest sums. This reduces both the time and space complexity.

How the Optimized Approach Works:

1. Perform BFS to traverse the tree level-by-level.
2. For each level, compute the sum of the node values.
3. Insert the sum into a min-heap of size k. If the heap exceeds k elements, remove the smallest element.
4. After processing all levels, the root of the min-heap contains the k-th largest sum.

long long kthLargestLevelSum(TreeNode* root, int k) {
    priority_queue<long, vector<long>, greater<long>> pq;
    queue<TreeNode*> queue;
    queue.push(root);
    
    while (!queue.empty()) {
        long sum = 0;
        long size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode* item = queue.front();
            queue.pop();
            sum += item->val;
            
            if (item->left) queue.push(item->left);
            if (item->right) queue.push(item->right);
        }
        pq.push(sum);
        if (pq.size() > k) pq.pop();  // Keep only the top k elements in the min-heap
    }
    
    if (pq.size() < k) return -1;
    
    return pq.top();  // The k-th largest element
}
        

Time and Space Complexity (Optimized Solution):

• Time Complexity: O(n log k), where n is the number of levels and k is the number of largest sums we need to track. Each insertion into the min-heap takes O(log k) instead of O(log n).
• Space Complexity: O(k) because the heap size is limited to k elements, which is much smaller than the number of levels in the tree.

Conclusion:

By switching from a max-heap to a min-heap and keeping the heap size fixed at k, we significantly reduce the time complexity from O(n log n) to O(n log k) and the space complexity from O(n) to O(k). This optimization is a great example of how small changes in data structure choices can have a huge impact on performance, especially for large trees.

This problem highlights the importance of understanding how heaps can be used to efficiently solve real-world problems involving ranked data.