Leetcode Daily Question 22/10/2024 - 2583. Kth Largest Sum in a Binary Tree

Problem Description:

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.

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


class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
      max_heap = []
      queue = deque([root])
      
      while queue:
        level_size = len(queue)
        curr_level_sum = 0
        for _ in range(level_size):
          node = queue.popleft()
          curr_level_sum += node.val
          if node.left:
            queue.append(node.left)
          if node.right:
            queue.append(node.right)
        heapq.heappush(max_heap, -curr_level_sum)
        
      if k > len(max_heap):
        return -1
      else:
        for _ in range(k - 1):
          heapq.heappop(max_heap)
          
      return - heapq.heappop(max_heap)

Explanation:

Since we need to know the sum of each level, we need to perform a level traversal. This means we can use BFS, or Breadth First Search, to do this.

We use a queue to store the information of each level and a curr_level_sum variable to store the sum of the current level.

To compare these sums, we can use a max heap. A heap structure stores the element in ascending order from smallest the the largest like a stack of books.

To create a max heap, we can invert all the positive integers.

Since each entry in the heap represents one level, we can check the length of the heap against k to know if a valid kth largest element exists.

If it does, then we pop the heap k - 1 times, and return the kth elements from the heap and invert it back as a positive integer.

def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
      max_heap = []
      queue = deque([root])
      
      while queue:
        level_size = len(queue)
        curr_level_sum = 0
        for _ in range(level_size):
          node = queue.popleft()
          curr_level_sum += node.val
          if node.left:
            queue.append(node.left)
          if node.right:
            queue.append(node.right)
        heapq.heappush(max_heap, -curr_level_sum)
        
      if k > len(max_heap):
        return -1
      else:
        for _ in range(k - 1):
          heapq.heappop(max_heap)
          
      return - heapq.heappop(max_heap)

The time complexity is O(n) as we traverse every node in the tree exactly once.

The space complexity is O(n) as the worst case is each of the n nodes occupy exactly one level.

The full solution can be found near the top of the page.