Introduction

In this blog post, we will explore how to solve the LeetCode problem "2583" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 kth 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: 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. Example 2: Input: root = [1,2,null,3], k = 1 Output: 3 Explanation: The largest level sum is 3. Constraints: The number of nodes in the tree is n. 2 <= n <= 105 1 <= Node.val <= 106 1 <= k <= n

Explanation

• Perform a level-order traversal of the binary tree to calculate the sum of nodes at each level.
  • Store the level sums in a list.
  • Sort the level sums in descending order and return the kth largest element. If the number of levels is less than k, return -1.

• Runtime Complexity: O(N + L log L), where N is the number of nodes in the tree and L is the number of levels in the tree. Storage Complexity: O(W + L), where W is the maximum width of the tree and L is the number of levels.

Code

    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 kthLargestLevelSum(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

    level_sums.sort(reverse=True)
    return level_sums[k - 1]