Kth Largest Sum in a Binary Tree

class Solution {
public:
    long findKthLargestSum(TreeNode* root, int k) {
        priority_queue<long, vector<long>, greater<long> > minHeap;

        queue<TreeNode*> levelNodes;
        levelNodes.push(root);
        while (!levelNodes.empty()) {
            int levelSize = levelNodes.size();
            long levelSum = 0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode* currentNode = levelNodes.front();
                levelNodes.pop();
                levelSum += currentNode->val;
                if (currentNode->left) {
                    levelNodes.push(currentNode->left);
                }
                if (currentNode->right) {
                    levelNodes.push(currentNode->right);
                }
            }
            minHeap.push(levelSum);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        if (minHeap.size() < k) return -1;
        return minHeap.top();
    }
};

To solve the problem of finding the Kth largest sum of level sums in a binary tree using C++:

1. Define a priority_queue with a min-heap configuration to store the level sums. Use priority_queue<long, vector<long>, greater<long>> minHeap; for efficient retrieval and storage of the smallest elements.

2. Utilize queue<TreeNode*> levelNodes; to manage the nodes at each level of the binary tree. Initialize it by pushing the root node.

3. Employ a standard BFS (Breadth-First Search) loop with while (!levelNodes.empty()). Within the loop, calculate the sum of values of nodes that are at the same level.

   • For each level of nodes, initialize long levelSum = 0; and iterate through all nodes at that current level. For each node, add its value to levelSum.

   • Add each child of the current node to the queue for subsequent level calculations.

4. After calculating levelSum, push it onto the min heap. Ensure that the size of the heap does not exceed k by popping the top (smallest) element if necessary.

5. After processing all levels, check if the min heap size is less than k, indicating there aren't enough levels. In such cases, return -1.

6. Otherwise, retrieve and return the top element of the min-heap, which represents the Kth largest level sum.

This solution methodically captures the sum of values at each level of a binary tree and maintains a controlled-size heap to efficiently track and retrieve the Kth largest sum, ensuring optimal performance and space utilization.

class Solution {

    public long findKthLargestSum(TreeNode root, int k) {
        PriorityQueue<Long> minHeap = new PriorityQueue<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            // Processing the current level
            int levelSize = queue.size();
            long levelSum = 0;
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                levelSum += node.val;
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            minHeap.add(levelSum);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.size() < k ? -1 : minHeap.peek();
    }
}

The provided Java solution aims to find the kth largest sum of levels in a binary tree. The following key steps encapsulate the method:

1. Initialize a PriorityQueue<Long> minHeap to store the level sums and maintain the smallest values on the top as it's a min-heap.

2. Use a Queue<TreeNode> queue to traverse the tree level-by-level, initiating the queue with the root node.

3. Inside the main while loop, process each level of the tree:

   • Determine the number of nodes (levelSize) at the current level.
   • Initialize levelSum to accumulate the values of nodes at each level.

4. Traverse through each node at the current level (levelSize). For each node:

   • Add the value of the node to levelSum.
   • If left child exists, enqueue it.
   • If right child exists, enqueue it.

5. Post level processing:

   • Add levelSum to minHeap.
   • Ensure minHeap does not hold more than k elements. If it does, remove the smallest element (top of the heap) to only retain the k largest level sums.

6. After processing all tree levels:

   • If minHeap contains fewer than k elements, return -1, indicating fewer than k levels.
   • Otherwise, return the top element of minHeap, which represents the kth largest sum among the level sums.

This solution efficiently captures the desired kth largest level sum by maintaining a bounded size for the heap and selectively keeping only the top sums.

class Solution:
    def findKthLargestSum(self, root, k):
        min_heap = []
        level_nodes = deque()
        level_nodes.append(root)

        while level_nodes:
            level_size = len(level_nodes)
            current_level_sum = 0
            for _ in range(level_size):
                current = level_nodes.popleft()
                current_level_sum += current.val
                if current.left:
                    level_nodes.append(current.left)
                if current.right:
                    level_nodes.append(current.right)

            heapq.heappush(min_heap, current_level_sum)
            if len(min_heap) > k:
                heapq.heappop(min_heap)
        return min_heap[0] if len(min_heap) == k else -1

The provided Python code defines a method to find the K-th largest sum of levels in a binary tree. This solution employs a breadth-first search (BFS) approach using a queue to traverse the binary tree levels and a min-heap to efficiently track the K largest sums. Here are the key steps in the algorithm:

1. Initialize min_heap to store the sums of tree levels.
2. Use a deque named level_nodes to perform a level-order traversal (BFS) of the tree. Start by appending the root node to level_nodes.
3. While level_nodes is not empty, calculate the sum of node values at the current level:
   • Determine the number of nodes level_size at the current level.
   • Traverse through these nodes, summing up their values and adding their children to level_nodes for the next level.
4. Push the sum of the current level to min_heap.
5. If the size of min_heap exceeds K, remove the smallest element using heapq.heappop to only keep the K largest sums.
6. After processing all levels, check the size of min_heap. If it matches K, return the smallest element in min_heap (which is the K-th largest sum). If not, return -1 as an error signaling insufficient levels.

This technique ensures that the algorithm efficiently maintains only the top K level sums in terms of size, resulting in an overall time complexity of O(N log K) where N is the total number of nodes in the binary tree.