Kth Largest Sum in a Binary Tree

lcpy gen -n 2583   # by problem number
lcpy gen -s kth_largest_sum_in_a_binary_tree   # by problem name

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are the following:
- Level 1: 5.
- Level 2: 8 + 9 = 17.
- Level 3: 2 + 1 + 3 + 7 = 13.
- Level 4: 4 + 6 = 10.
The 2nd largest level sum is 13.

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The largest level sum is 3.

from collections import deque

from leetcode_py import TreeNode


class Solution:
    # Time: O(n)
    # Space: O(w)
    def kth_largest_level_sum(self, root: TreeNode[int] | None, k: int) -> int:
        sums: list[int] = []
        queue = deque([root] if root is not None else [])
        while queue:
            level_sum = 0
            for _ in range(len(queue)):
                node = queue.popleft()
                level_sum += node.val
                if node.left is not None:
                    queue.append(node.left)
                if node.right is not None:
                    queue.append(node.right)
            sums.append(level_sum)
        if k > len(sums):
            return -1
        sums.sort(reverse=True)
        return sums[k - 1]