# Kth Largest Sum in a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/kth-largest-sum-in-a-binary-tree
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
---
## Problem
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:**

![](https://assets.glich.co/dsa/kth-largest-sum-in-a-binary-tree/image0.png) 

**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:**

![](https://assets.glich.co/dsa/kth-largest-sum-in-a-binary-tree/image1.png) 

**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 <= 105`
* `1 <= Node.val <= 106`
* `1 <= k <= n`

# Approaches
## Breadth-First Search (BFS) and Sorting
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.
**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.
**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.
### Explanation
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`.

```java
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);
    }
}
```
### 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.

## Breadth-First Search (BFS) with a Min-Heap
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.
**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.
**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.
### Explanation
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.

```java
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;
        }

        // A min-heap to store the k largest level sums
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        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);
                }
            }
            
            minHeap.offer(currentLevelSum);
            if (minHeap.size() > k) {
                minHeap.poll(); // Remove the smallest element
            }
        }

        if (minHeap.size() < k) {
            return -1;
        }

        return minHeap.peek();
    }
}
```
### 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.

# Solutions
### Java

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

### CPP

```cpp
/** * 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 ]; } };
```

### Python

```python
# 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 ]
```