LeetCode Solutions Blog

Kth Largest Sum in a Binary Tree

Number: 2646

Difficulty: Medium

Paid? No

Problem Description

Given the root of a binary tree and a positive integer k, the task is to compute the sum of node values for each level in the tree. Then, return the kth largest level sum (levels are counted from root, and kth largest implies ordering the sums in descending order). If the number of levels is less than k, return -1.

Key Insights

We use a Breadth-first Search (BFS) to traverse the tree level by level.
For each level, compute the sum of all node values.
Collect all level sums, and then sort them in descending order to pick the kth largest sum.
Edge case: if the tree has fewer than k levels, then return -1.

Space and Time Complexity

Time Complexity: O(n log n) in the worst-case scenario (when the tree is skewed so that there are O(n) levels and sorting these level sums takes O(n log n)). Space Complexity: O(n) for storing the level sums and using a queue during the BFS.

Solution

The solution begins by performing a level-order (BFS) traversal of the tree. During each level of the traversal, all nodes are processed and their values summed up. These sums are stored in a list. Once the traversal is complete, the list of sums is sorted in descending order. The kth largest element is then accessed from this sorted list. If k exceeds the number of levels present, the function returns -1.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def kthLargestLevelSum(root: TreeNode, k: int) -> int:
    # Edge case: if the tree is empty, return -1.
    if not root:
        return -1

    from collections import deque
    # Initialize the queue for level order traversal.
    queue = deque([root])
    level_sums = []
    
    # Perform BFS.
    while queue:
        level_length = len(queue)
        level_sum = 0  # Sum for the current level.
        # Process all nodes in the current level.
        for _ in range(level_length):
            node = queue.popleft()
            level_sum += node.val
            # Add child nodes to the queue if they exist.
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # Append the computed level sum to the list.
        level_sums.append(level_sum)
    
    # Check if there are at least k levels.
    if k > len(level_sums):
        return -1
    
    # Sort the level sums in descending order.
    level_sums.sort(reverse=True)
    # Return the kth largest level sum.
    return level_sums[k - 1]
    
# Example usage:
# Construct the tree [5,8,9,2,1,3,7,4,6] and call kthLargestLevelSum(root, 2)