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:
n.2 <= n <= 1051 <= Node.val <= 1061 <= k <= nIn 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.
C++
Java
C#
JavaScript
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.
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.
C++
Java
C#
JavaScript
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 | 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). |
Kth Largest Sum in a Binary Tree - Leetcode 2583 - Python • NeetCodeIO • 7,349 views views
Watch 9 more video solutions →Practice Kth Largest Sum in a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode