Kth Largest Sum in a Binary Tree

You are given the root of a binary tree and a positive integer k.

The level sum in the tree is the sum of the values of the nodes that are on the same level.

Return the k^th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Note that two nodes are on the same level if they have the same distance from the root.

Example 1

        5
       / \
      /   \
     8     9
    / \   / \
   2   1 3   7
  / \
 4   6

Inputroot = [5,8,9,2,1,3,7,4,6], k = 2

Output13

The level sums are 5, 17, 13, and 10, so the 2nd largest level sum is 13.

Example 2

Inputroot = [1,2,null,3], k = 1

Output3

The largest level sum is 3.

Constraints