Kth Largest Sum in a Binary Tree

Med

#2363Time: 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.

Algorithms

Sorting Breadth-First Search

Data structures

Tree Binary Tree

Prompt

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.

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 <= 10⁵
1 <= Node.val <= 10⁶
1 <= 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 levelSums to store the sum of each level.
Initialize a queue and add the root node.
Perform a level-order traversal (BFS):
- While the queue is not empty, determine the number of nodes at the current level (levelSize).
- Initialize currentLevelSum to 0.
- Dequeue levelSize nodes, add their values to currentLevelSum, and enqueue their children.
- Add currentLevelSum to the levelSums list.
After the traversal, check if levelSums.size() is less than k. If so, return -1.
Sort levelSums in descending order.
Return the element at index k-1 from 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.

1import java.util.*;2 3/**4 * Definition for a binary tree node.5 * public class TreeNode {6 *     int val;7 *     TreeNode left;8 *     TreeNode right;9 *     TreeNode() {}10 *     TreeNode(int val) { this.val = val; }11 *     TreeNode(int val, TreeNode left, TreeNode right) {12 *         this.val = val;13 *         this.left = left;14 *         this.right = right;15 *     }16 * }17 */18class Solution {19    public long kthLargestLevelSum(TreeNode root, int k) {20        if (root == null) {21            return -1;22        }23 24        List<Long> levelSums = new ArrayList<>();25        Queue<TreeNode> queue = new LinkedList<>();26        queue.offer(root);27 28        while (!queue.isEmpty()) {29            int levelSize = queue.size();30            long currentLevelSum = 0;31            for (int i = 0; i < levelSize; i++) {32                TreeNode node = queue.poll();33                currentLevelSum += node.val;34                if (node.left != null) {35                    queue.offer(node.left);36                }37                if (node.right != null) {38                    queue.offer(node.right);39                }40            }41            levelSums.add(currentLevelSum);42        }43 44        if (levelSums.size() < k) {45            return -1;46        }47 48        Collections.sort(levelSums, Collections.reverseOrder());49        return levelSums.get(k - 1);50    }51}

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.

This approach optimizes the process of finding the kth largest element by using a min-heap (Priority Queue) of size k. Instead of storing all level sums and then sorting, we maintain the k largest sums encountered so far during the BFS traversal. This avoids the cost of a full sort.

Algorithm

Initialize a min-heap minHeap of size k.
Initialize a queue for BFS and add the root node.
Perform a level-order traversal (BFS):
- While the queue is not empty, calculate the currentLevelSum for the current level.
- Add currentLevelSum to minHeap.
- If minHeap.size() is greater than k, remove the smallest element from the heap (minHeap.poll()).
After the traversal, check if minHeap.size() is less than k. If so, return -1.
The top of the min-heap (minHeap.peek()) is the kth largest sum. Return this value.

Walkthrough

Similar to the first approach, we use BFS to traverse the tree and calculate level sums. We initialize a min-heap. A min-heap is a data structure that always keeps the smallest element at the top, making it efficient to access and remove. As we calculate the sum for each level, we add it to the min-heap. To ensure the heap only stores the k largest elements, we check its size after each insertion. If the size becomes k + 1, we remove the smallest element (the root of the min-heap), which takes logarithmic time. By the end of the BFS traversal, the min-heap will contain the k largest level sums from the entire tree. Finally, we check if the heap's size is less than k. If it is, it means the tree had fewer than k levels, and we return -1. Otherwise, the kth largest sum is the smallest element among the top k sums, which is exactly the element at the top of our min-heap. We return this value.

1import java.util.*;2 3/**4 * Definition for a binary tree node.5 * public class TreeNode {6 *     int val;7 *     TreeNode left;8 *     TreeNode right;9 *     TreeNode() {}10 *     TreeNode(int val) { this.val = val; }11 *     TreeNode(int val, TreeNode left, TreeNode right) {12 *         this.val = val;13 *         this.left = left;14 *         this.right = right;15 *     }16 * }17 */18class Solution {19    public long kthLargestLevelSum(TreeNode root, int k) {20        if (root == null) {21            return -1;22        }23 24        // A min-heap to store the k largest level sums25        PriorityQueue<Long> minHeap = new PriorityQueue<>();26        Queue<TreeNode> queue = new LinkedList<>();27        queue.offer(root);28 29        while (!queue.isEmpty()) {30            int levelSize = queue.size();31            long currentLevelSum = 0;32            for (int i = 0; i < levelSize; i++) {33                TreeNode node = queue.poll();34                currentLevelSum += node.val;35                if (node.left != null) {36                    queue.offer(node.left);37                }38                if (node.right != null) {39                    queue.offer(node.right);40                }41            }42            43            minHeap.offer(currentLevelSum);44            if (minHeap.size() > k) {45                minHeap.poll(); // Remove the smallest element46            }47        }48 49        if (minHeap.size() < k) {50            return -1;51        }52 53        return minHeap.peek();54    }55}

Complexity

Time

O(N + L log k), where N is the number of nodes, L is the number of levels, and k is the given integer. The BFS traversal is O(N). For each of the L levels, we perform a heap operation which takes O(log k) time. This is more efficient than the sorting approach, especially when L is large and k is small.

Space

O(N). The space is dominated by the queue used for BFS, which can be O(N) in the worst case. The min-heap requires O(k) space.

Trade-offs

Pros

More time-efficient than the sorting approach as it avoids a full sort.
Finds the kth largest element "on-the-fly" during the traversal.

Cons

Slightly more complex to implement due to the use of a heap.
The space complexity is still dominated by the BFS queue, so there's no space improvement over the sorting approach.

Solutions

Solution

1/** * 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 ); } }

1/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: long long kthLargestLevelSum ( TreeNode * root , int k ) { vector < long long > arr ; queue < TreeNode *> q { { root } }; while ( ! q . empty ()) { long long t = 0 ; for ( int n = q . size (); n ; -- n ) { root = q . front (); q . pop (); t += root -> val ; if ( root -> left ) { q . push ( root -> left ); } if ( root -> right ) { q . push ( root -> right ); } } arr . push_back ( t ); } if ( arr . size () < k ) { return - 1 ; } sort ( arr . rbegin (), arr . rend ()); return arr [ k - 1 ]; } };

1# 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 class Solution : def kthLargestLevelSum ( self , root : Optional [ TreeNode ], k : int ) -> int : arr = [] q = deque ([ root ]) while q : t = 0 for _ in range ( len ( q )): root = q . popleft () t += root . val if root . left : q . append ( root . left ) if root . right : q . append ( root . right ) arr . append ( t ) return - 1 if len ( arr ) < k else nlargest ( k , arr )[ - 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.

← Previous

Previous problem

Next problem