Kth Largest Sum in a Binary Tree

For each depth of the binary tree, add the values of all nodes at that depth. Return the kth largest of these level sums.

Equal sums occupy separate positions in the ranking. If the tree has fewer than k levels, return -1. The root is at depth 0, and each child is one level deeper than its parent.

Examples use level-order arrays. After the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted.

Example 1:

Input: root = [4,7,2,3,5]
k = 2

Output: 8

Explanation: The level sums from top to bottom are 4, 9, and 8. In descending order they are 9, 8, and 4, so the second largest is 8.

Example 2:

Input: root = [6,2,4]
k = 2

Output: 6

Explanation: The root level sums to 6, and the next level also sums to 6. Both sums count separately, so the second largest is 6.

Example 3:

Input: root = [9,1,2]
k = 3

Output: -1

Explanation: This tree has only two levels. There is no third level sum to rank, so return -1.

Constraints:

• The tree has n nodes, where 2 <= n <= 100000.
• 1 <= Node.val <= 1000000
• 1 <= k <= n
• Level sums can exceed the range of a 32-bit signed integer.