Kth Largest Sum in a Binary Tree - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: You are given the root of a binary tree. Each level of the tree has a sum formed by adding the values of all nodes on that level. The task is to compute every level sum and return the kth largest among them. If the tree has fewer than k levels, return -1.
Approach 1: Breadth-First Search with Min-Heap (O(n log k) time, O(w + k) space)
This approach processes the tree level by level using Breadth-First Search. Use a queue to iterate through each level and compute the sum of node values at that level. Instead of storing every level sum, maintain a min-heap of size k. After computing a level sum, push it into the heap; if the heap size exceeds k, remove the smallest element. The heap always stores the k largest level sums seen so far, and the root of the heap is the kth largest. This reduces sorting overhead and avoids storing all sums when the tree has many levels.
The time complexity is O(n log k) because every node is visited once and each heap operation costs log k. Space complexity is O(w + k), where w is the maximum tree width due to the BFS queue. This approach is typically the most efficient when k is much smaller than the number of levels.
Approach 2: Depth-First Search with Level Tracking (O(n + L log L) time, O(L) space)
This approach uses tree traversal with DFS while tracking the current depth. Maintain an array (or hash map) where the index represents the level and the value stores the cumulative sum of nodes at that level. During recursion, add the node value to the corresponding level entry. If the level does not exist yet, append a new entry.
After the traversal completes, the array contains all level sums. Sort the array in descending order using a standard sorting algorithm and return the element at index k - 1. If the array length is smaller than k, return -1. DFS visits each node exactly once, giving O(n) traversal time. Sorting the L level sums adds O(L log L), where L is the number of levels.
This method is straightforward and easy to implement. It works well when the number of levels is relatively small and when you prefer recursive traversal over queue-based iteration.
Recommended for interviews: BFS with a min-heap is usually the expected optimal solution. It demonstrates strong understanding of binary tree traversal and heap optimization. A brute-force style solution that collects all sums and sorts them shows basic problem understanding, but maintaining a heap of size k proves you can reduce unnecessary work and control memory usage.
Approach 1: Breadth-First Search (BFS) with Min-Heap
In this approach, we utilize Breadth-First Search (BFS) to traverse the binary tree level by level. As we traverse each level, we compute the sum of the node values at that level. We store these sums in a min-heap of size 'k'. If the heap grows beyond size 'k', we remove the smallest element, ensuring that at the end, the heap contains the 'k' largest level sums. This allows us to efficiently retrieve the kth largest level sum by looking at the top of the min-heap.
This Python solution uses BFS to iterate over each level of the tree, computes the sum of each level, and maintains the 'k' largest sums using a min-heap.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n log k), where 'n' is the number of nodes in the tree. We traverse all nodes once, and each heap operation takes O(log k).
Space Complexity: O(max(w, k)), where 'w' is the maximum width of the tree at any level (for the queue), and 'k' is the size of the heap.
Approach 2: Depth-First Search (DFS) with Level Tracking
This approach utilizes a depth-first search (DFS) technique with a modification that tracks and accumulates the sum values per level in an array or list. Once all levels are processed with DFS, we sort the resulting list of sums. If the list has fewer than 'k' entries, we return -1; otherwise, we return the k-th largest value by accessing the list.
This Python solution performs a DFS while maintaining a level-specific accumulation of sums. After complete traversal and sum computation, we sort and pick the k-th largest sum.
Code
Python
C++
Java
C#
JavaScript
Complexity
Time Complexity: O(n + d log d), where 'n' is the number of nodes and 'd' is the depth of the tree (to sort the level sums).
Space Complexity: O(d), representing the recursion stack and array for level sums, where 'd' is tree depth.
Approach 3: BFS + Sorting
We can use BFS to traverse the binary tree, while recording the sum of nodes at each level, then sort the array of node sums, and finally return the kth largest node sum. Note that if the number of levels in the binary tree is less than k, then return -1.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Approach 4: DFS + Sorting
We can also use DFS to traverse the binary tree, while recording the sum of nodes at each level, then sort the array of node sums, and finally return the kth largest node sum. Note that if the number of levels in the binary tree is less than k, then return -1.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) with Min-Heap | Time Complexity: O(n log k), where 'n' is the number of nodes in the tree. We traverse all nodes once, and each heap operation takes O(log k). |
| Depth-First Search (DFS) with Level Tracking | Time Complexity: O(n + d log d), where 'n' is the number of nodes and 'd' is the depth of the tree (to sort the level sums). |
| BFS + Sorting | — |
| DFS + Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Min-Heap | O(n log k) | O(w + k) | Best general solution when k is small relative to number of levels |
| DFS with Level Tracking + Sort | O(n + L log L) | O(L) | Simpler implementation when storing all level sums is acceptable |
| BFS + Collect and Sort | O(n + L log L) | O(L) | Straightforward approach when optimization is not required |
Video Solution
Kth Largest Sum in a Binary Tree - Leetcode 2583 - Python • NeetCodeIO • 8,108 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Kth Largest Sum in a Binary Tree easy or hard?
Kth Largest Sum in a Binary Tree Python/Java solution
How to solve Kth Largest Sum in a Binary Tree in O(n)?
What is the best approach for Kth Largest Sum in a Binary Tree?
Is Kth Largest Sum in a Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Kth Largest Sum in a Binary Tree?
What is the time complexity of Kth Largest Sum in a Binary Tree?
Ready to solve this problem?
Practice Kth Largest Sum in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode