Kth Largest Sum in a Binary Tree

Use BFS because each queue layer corresponds to one tree level. At the start of a round, capture levelSize = queue.length, remove exactly that many nodes, sum their values, and enqueue their non-null children. Feed each completed level sum into a min-heap of size at most k; if it exceeds k, remove the smallest. After traversal, the root is the kth largest level sum if there were at least k levels, otherwise return the specified sentinel. Sorting all level sums is simpler and costs O(h log h), but the heap reduces selection storage to O(k), where h is tree height. Be careful not to use the changing queue length as the current level boundary. Negative node values mean sums and heap comparisons must support negatives, and totals may exceed ordinary integer range. Test an empty tree, one level, a skewed tree, equal level sums, k=1, and k larger than height. Time is O(n log k) with O(width+k) space.