We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Largest Sum in a Binary Tree

Difficulty: Medium

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 k-th largest level sum in the tree (not necessarily distinct). If there are fewer than k levels in the tree, return -1.

Key Insights

  • The sum of node values on the same level can be calculated using a level-order traversal (BFS).
  • We can utilize a max-heap or sort the level sums to determine the k-th largest sum.
  • The constraints allow for a maximum of 100,000 nodes, indicating that the solution should be efficient in both time and space.

Space and Time Complexity

Time Complexity: O(n log n) - where n is the number of levels, due to sorting the level sums. Space Complexity: O(n) - space used for storing level sums.

Solution

To solve this problem, we can perform a level-order traversal (BFS) of the binary tree to calculate the sum of values at each level. We can store these sums in a list. After obtaining all level sums, we can sort the list in descending order and return the k-th element. If the number of levels is less than k, we return -1.

Code Solutions

from collections import deque

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)
        
    # Sort level sums in descending order
    level_sums.sort(reverse=True)
    
    # Return the k-th largest level sum or -1 if not enough levels
    return level_sums[k - 1] if k <= len(level_sums) else -1
← Back to All Questions