LeetCode 2583: Kth Largest Sum in a Binary Tree Solution

Master LeetCode problem 2583 (Kth Largest Sum in a Binary Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2583. Kth Largest Sum in a Binary Tree

Medium

Tree Breadth-First Search Sorting Binary Tree

Problem Explanation

Explanation

To find the kth largest level sum in a binary tree, we can perform a level order traversal of the tree while keeping track of the sum of nodes at each level. Then we can sort the level sums in descending order and return the kth largest sum.

Algorithm:

Perform a level order traversal of the binary tree and calculate the sum of nodes at each level.
Store the level sums in a priority queue to maintain the k largest sums.
After traversing all levels, pop the top element from the priority queue k times to get the kth largest level sum.

Time Complexity: O(n log k) where n is the number of nodes in the tree. Space Complexity: O(k) for the priority queue to store k largest sums.

Solution Code

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public int kthLargestLevelSum(TreeNode root, int k) {
    if (root == null) return -1;
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    
    PriorityQueue<Integer> pq = new PriorityQueue<>(k, Collections.reverseOrder());
    
    while (!queue.isEmpty()) {
        int size = queue.size();
        int levelSum = 0;
        
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            levelSum += node.val;
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        
        pq.offer(levelSum);
    }
    
    if (pq.size() < k) return -1;
    
    int result = 0;
    for (int i = 0; i < k; i++) {
        result = pq.poll();
    }
    
    return result;
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2583 (Kth Largest Sum in a Binary Tree)?

This page provides optimized solutions for LeetCode problem 2583 (Kth Largest Sum in a Binary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2583 (Kth Largest Sum in a Binary Tree)?

The time complexity for LeetCode 2583 (Kth Largest Sum in a Binary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2583 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2583 in Java, C++, or Python.

Back to LeetCode Solutions