Kth Largest Sum in a Binary Tree
MedPrompt
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 <= 1051 <= Node.val <= 1061 <= k <= n
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first calculates all the level sums and then finds the kth largest one. We can use a Breadth-First Search (BFS) to traverse the tree level by level. During the traversal, we compute the sum of node values for each level and store these sums in a list. After the traversal is complete, we sort the list of sums in descending order and pick the element at the k-1th index.
Algorithm
- Initialize an empty list
levelSumsto store the sum of each level. - Initialize a queue and add the
rootnode. - Perform a level-order traversal (BFS):
- While the queue is not empty, determine the number of nodes at the current level (
levelSize). - Initialize
currentLevelSumto 0. - Dequeue
levelSizenodes, add their values tocurrentLevelSum, and enqueue their children. - Add
currentLevelSumto thelevelSumslist.
- While the queue is not empty, determine the number of nodes at the current level (
- After the traversal, check if
levelSums.size()is less thank. If so, return -1. - Sort
levelSumsin descending order. - Return the element at index
k-1from the sorted list.
Walkthrough
The core idea is to separate the problem into two parts: calculating level sums and then finding the kth largest among them. We use a queue, a standard tool for BFS. We start by adding the root node to the queue. The main loop of the BFS runs as long as the queue is not empty. Inside this loop, we have another loop that processes all nodes at the current level. To do this, we first record the number of nodes currently in the queue (levelSize). We iterate levelSize times, dequeuing a node, adding its value to a currentLevelSum, and enqueuing its children. Once the inner loop finishes, currentLevelSum holds the total sum for that level, which we add to a list called levelSums. After the BFS completes, we have a list of all level sums. We check if the number of levels is less than k. If it is, we return -1. Otherwise, we sort the levelSums list and return the element at index k-1.
import java.util.*; /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public long kthLargestLevelSum(TreeNode root, int k) { if (root == null) { return -1; } List<Long> levelSums = new ArrayList<>(); Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); long currentLevelSum = 0; for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); currentLevelSum += node.val; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } levelSums.add(currentLevelSum); } if (levelSums.size() < k) { return -1; } Collections.sort(levelSums, Collections.reverseOrder()); return levelSums.get(k - 1); }}Complexity
Time
O(N + L log L), where N is the number of nodes and L is the number of levels. The BFS traversal takes O(N) time. Sorting the L level sums takes O(L log L) time. In the worst case (a skewed tree), L can be up to N, making the complexity O(N log N).
Space
O(N). The queue for BFS can store up to O(N) nodes in the worst case (for a complete binary tree, the last level has ~N/2 nodes). The `levelSums` list stores L sums, which is O(N) in the worst case.
Trade-offs
Pros
Simple and straightforward to implement.
Clearly separates the logic of traversal and finding the kth element.
Cons
The sorting step can be inefficient, especially if the number of levels (L) is large. We sort all L sums even though we only need the kth largest one.
Solutions
Solution
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public long kthLargestLevelSum ( TreeNode root , int k ) { List < Long > arr = new ArrayList <>(); Deque < TreeNode > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { long t = 0 ; for ( int n = q . size (); n > 0 ; -- n ) { root = q . pollFirst (); t += root . val ; if ( root . left != null ) { q . offer ( root . left ); } if ( root . right != null ) { q . offer ( root . right ); } } arr . add ( t ); } if ( arr . size () < k ) { return - 1 ; } Collections . sort ( arr , Collections . reverseOrder ()); return arr . get ( k - 1 ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.