#2583

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Kth Largest Sum in a Binary Tree

Find the kth largest level sum in a binary tree using level-order traversal and sorting.

tree breadth first search sorting binary tree

Problem Statement

You are given the root of a binary tree and a positive integer k. Your task is to compute the sum of node values at each level of the tree. Then, return the kth largest sum from these levels. If there are fewer than k levels, return -1.

Perform a level-order traversal to compute the level sums. After collecting the sums, use a sorting algorithm or a heap to efficiently find the kth largest sum. The problem emphasizes binary-tree traversal combined with state tracking to process level sums.

Examples

Example 1

Input: root = [5,8,9,2,1,3,7,4,6], k = 2

Output: 13

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

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

Solution Approach

Level-order Traversal

Start by performing a level-order traversal using a queue. For each level, calculate the sum of all node values on that level. Store these sums in an array or list.

Sorting or Heap Approach

Once all level sums are computed, sort the list of sums in descending order or use a min-heap to keep track of the kth largest sum efficiently. If using sorting, the kth largest sum is the element at index k-1.

Return the Result

After sorting or heap processing, return the kth largest sum. If the number of levels is less than k, return -1 as the result.

Complexity Analysis

Metric	Value
Time	O(N \cdot \log k)
Space	O(N)

The time complexity is O(N * log k), where N is the number of nodes, because we perform a level-order traversal and then process the sums with a sorting or heap operation. The space complexity is O(N) as we need to store the level sums for each level of the tree.

What Interviewers Usually Probe

Candidate should demonstrate an understanding of level-order traversal and its application to binary trees.
The candidate should show how to handle the kth largest selection with efficient sorting or heap techniques.
Pay attention to how well the candidate handles edge cases such as fewer than k levels.

Common Pitfalls or Variants

Common pitfalls

Incorrectly counting or summing nodes at each level due to improper traversal logic.
Using inefficient sorting or heap techniques, leading to higher time complexity than necessary.
Failing to handle the edge case where the tree has fewer than k levels, resulting in incorrect results.

Follow-up variants

Finding the kth smallest level sum instead of the kth largest.
Handling trees with missing nodes at certain levels (e.g., incomplete trees).
Optimizing space complexity when storing level sums for large trees.

FAQ

What is the primary algorithmic pattern for the Kth Largest Sum in a Binary Tree problem?

The problem relies on binary-tree traversal (level-order) combined with state tracking (level sums) and sorting or heap selection to find the kth largest sum.

How do I handle fewer than k levels in the tree?

If the tree has fewer than k levels, return -1 as the result. Ensure you count the actual number of levels correctly during traversal.

What is the time complexity of the solution for this problem?

The time complexity is O(N * log k), where N is the number of nodes and k is the number of levels you're interested in. This accounts for the traversal and sorting/heap operations.

Can I optimize the space complexity for this problem?

Space complexity can be optimized by using a heap instead of storing all level sums, but it still depends on the structure of the tree and the value of k.

Is there a more efficient approach than sorting to find the kth largest level sum?

Yes, using a min-heap with size k allows you to efficiently track the kth largest sum in O(N * log k) time complexity without needing to fully sort the sums.

terminal

Solution

Solution 1: 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 $k$th largest node sum. Note that if the number of levels in the binary tree is less than $k$, then return $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

Solution 2: 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 $k$th largest node sum. Note that if the number of levels in the binary tree is less than $k$, then return $-1$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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

Continue Practicing

#2641 cousins in binary tree ii #2471 minimum number of operations to sort a binary tree by level #2458 height of binary tree after subtree removal queries