Question

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<sup>th</sup> 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:

If the input is root = [5,8,9,2,1,3,7,4,6], k = 2, the expected output is 13 because the level sums are 5, 17, 13, and 10. The 2nd largest of these is 13.

Example 2:

If the input is root = [1,2,null,3], k = 1, the expected output is 3 because the largest level sum is 3.

Constraints:

The number of nodes in the tree is n.
2 <= n <= 10^5
1 <= Node.val <= 10^6
1 <= k <= n

Can you provide an efficient algorithm to solve this problem?

# Kth Largest Level Sum in a Binary Tree

## Problem Description

Given the `root` of a binary tree and a positive integer `k`, the task is to find the k-th largest level sum in the tree. The level sum is the sum of the values of nodes at the same level. If there are fewer than `k` levels in the tree, return -1.

**Example 1:**

Input: root = [5,8,9,2,1,3,7,4,6], k = 2 Output: 13


**Example 2:**

Input: root = [1,2,null,3], k = 1 Output: 3


## Naive Approach

The naive approach involves performing a level-order traversal of the binary tree, calculating the sum of nodes at each level, and then sorting these level sums to find the k-th largest sum.

### Code (Python)

```python
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_largest_level_sum_naive(root, k):
    if not root:
        return -1

    level_sums = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level_sum = 0
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        level_sums.append(level_sum)

    level_sums.sort(reverse=True)

    if len(level_sums) < k:
        return -1
    else:
        return level_sums[k-1]

Optimal Approach

Using a min-heap (priority queue) of size k to keep track of the k largest level sums encountered so far. For each level sum, compare it with the smallest element in the min-heap. If the current level sum is larger, replace the smallest element with the current sum.

Code (Python)

import heapq
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kth_largest_level_sum_optimal(root, k):
    if not root:
        return -1

    level_sums = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level_sum = 0
        for _ in range(level_size):
            node = queue.popleft()
            level_sum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        level_sums.append(level_sum)

    if len(level_sums) < k:
        return -1

    min_heap = level_sums[:k]
    heapq.heapify(min_heap)

    for i in range(k, len(level_sums)):
        if level_sums[i] > min_heap[0]:
            heapq.heapreplace(min_heap, level_sums[i])

    return min_heap[0]

Big(O) Runtime Analysis

Naive Approach:
- Level-order traversal: O(N), where N is the number of nodes in the tree.
- Sorting: O(M log M), where M is the number of levels in the tree. In the worst case M can be N. Therefore, O(N log N).
- Total: O(N + N log N) = O(N log N)
Optimal Approach:
- Level-order traversal: O(N).
- Building initial heap: O(k).
- Iterating through remaining levels: O((M-k) log k), where M is the number of levels. In the worst case M can be N.
- Total: O(N + k + (N-k) log k) = O(N + Nlogk) = O(Nlogk)

Big(O) Space Usage Analysis

Naive Approach:
- Queue for level-order traversal: O(W), where W is the maximum width of the tree.
- Storing level sums: O(M), where M is the number of levels.
- Total: O(W + M). In the worst case, W = N and M = N. Therefore, O(N)
Optimal Approach:
- Queue for level-order traversal: O(W).
- Min-heap: O(k).
- Storing level sums: O(M), where M is the number of levels.
- Total: O(W + k + M). In the worst case, W = N and M = N. Therefore, O(N + k) = O(N).

Edge Cases

Empty Tree:
- If the input tree is empty (root is None), return -1.
k is greater than the number of levels:
- If k is larger than the number of levels in the tree, return -1.
Large Tree:
- The tree has a large number of nodes. The solution should handle large trees efficiently to avoid time limit exceeded errors.
Skewed Tree:
- The tree is heavily skewed to one side. The level-order traversal should still work correctly.
Negative Node Values:
- The node values are negative. Ensure that the sum is calculated correctly, even with negative values.
Zero Node Values:
- The node values are zero. Ensure that this does not cause any division by zero errors or incorrect sum calculations.

These edge cases are handled in both the naive and optimal approaches by the initial checks and the logic within the level-order traversal.

Kth Largest Sum in a Binary Tree