LeetCode 2583 - Kth Largest Sum in a Binary Tree

LeetCode Problem 2583

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Sorting, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary tree and an integer k. For every level in the tree, we calculate the sum of all node values that appear on that level. After computing all level sums, we must return the kth largest level sum.

A binary tree level is determined by the distance from the root. The root itself is on level 0, its children are on level 1, their children are on level 2, and so on. Nodes that share the same depth belong to the same level.

For example, if a level contains the nodes [2, 1, 3, 7], then the level sum is:

2 + 1 + 3 + 7 = 13

The problem specifically says that the sums do not need to be distinct. That means duplicate sums are counted separately when determining the kth largest value.

The constraints are important:

• The tree can contain up to 10^5 nodes
• Node values can be as large as 10^6
• k can also be as large as 10^5

These limits immediately tell us that we need an efficient traversal. Any algorithm worse than roughly O(n log n) may struggle at the upper bound.

An important observation is that level order traversal naturally groups nodes by depth. Breadth-First Search, BFS, is therefore a very natural fit for this problem.

Several edge cases are worth considering upfront:

• The tree may contain only one level
• k may be larger than the number of levels, in which case we must return -1
• Multiple levels may have the same sum
• The tree may be extremely unbalanced, behaving almost like a linked list
• Level sums can become very large, especially in Go, so using int64 is important

Approaches

Brute Force Approach

A brute force solution would first compute the depth of every node individually. For each possible level, we could run another traversal to sum all nodes that belong to that level.

For example:

1. Compute the tree height
2. For every level from 0 to height
3. Traverse the entire tree again to collect nodes at that depth
4. Store the level sum
5. Sort all sums and return the kth largest

This approach is correct because every level is processed independently and all sums are computed accurately.

However, it is inefficient. If the tree has height h, and we traverse the tree once for every level, the total complexity becomes approximately O(n * h). In the worst case, a skewed tree has height n, producing O(n^2) time complexity.

With 10^5 nodes, this is far too slow.

Optimal Approach

The key insight is that Breadth-First Search already processes the tree level by level.

Instead of repeatedly traversing the tree, we can perform a single BFS traversal:

1. Use a queue to process nodes level by level
2. For each level, compute the sum while removing nodes from the queue
3. Store each level sum
4. Sort the collected sums in descending order
5. Return the kth largest value

This works efficiently because every node is visited exactly once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly traverses the tree for each level
Optimal	O(n + L log L)	O(L + w)	Single BFS traversal, where L is number of levels and w is maximum width

Here:

• L is the number of levels
• w is the maximum number of nodes stored in the queue at once

Algorithm Walkthrough

Step 1: Initialize a queue for BFS

We use a queue because BFS processes nodes level by level naturally. Start by placing the root node into the queue.

Step 2: Process one level at a time

At the beginning of each iteration, the queue contains exactly the nodes of the current level.

We record the current queue size because that tells us how many nodes belong to this level.

Step 3: Compute the level sum

Remove exactly level_size nodes from the queue.

For each node:

• Add its value to the current level sum
• Push its left child into the queue if it exists
• Push its right child into the queue if it exists

After processing all nodes for the current level, we have the complete sum for that level.

Step 4: Store the level sum

Append the computed sum into a list of level sums.

Step 5: Repeat until traversal finishes

Continue the BFS process until the queue becomes empty.

At that point, all levels have been processed exactly once.

Step 6: Check whether k is valid

If the number of levels is smaller than k, return -1.

Step 7: Sort the level sums

Sort the sums in descending order.

The kth largest sum is then located at index k - 1.

Why it works

BFS guarantees that nodes are processed level by level. At the start of each iteration, the queue contains only nodes from the same depth. By processing exactly the current queue size, we isolate one level completely before moving to the next.

Because every node is visited once and contributes exactly once to its corresponding level sum, the resulting list contains all correct level sums. Sorting these sums allows direct retrieval of the kth largest value.

Python Solution

from collections import deque
from typing import Optional

# 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:
        queue = deque([root])
        level_sums = []

        while queue:
            level_size = len(queue)
            current_sum = 0

            for _ in range(level_size):
                node = queue.popleft()
                current_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            level_sums.append(current_sum)

        if len(level_sums) < k:
            return -1

        level_sums.sort(reverse=True)

        return level_sums[k - 1]

The implementation follows the BFS algorithm directly.

The queue is initialized with the root node. During each iteration of the outer loop, we process one full level. The variable level_size captures how many nodes belong to the current level, ensuring we do not accidentally mix nodes from different depths.

The variable current_sum accumulates the values of all nodes in the current level. While processing nodes, we also enqueue their children so the next iteration can process the next level.

After all levels are processed, the list level_sums contains every level sum in the tree. We verify that at least k levels exist. If not, we return -1.

Finally, we sort the sums in descending order and return the element at index k - 1.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "sort"

func kthLargestLevelSum(root *TreeNode, k int) int64 {
    queue := []*TreeNode{root}
    levelSums := []int64{}

    for len(queue) > 0 {
        levelSize := len(queue)
        var currentSum int64 = 0

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

            currentSum += int64(node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }

            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        levelSums = append(levelSums, currentSum)
    }

    if len(levelSums) < k {
        return -1
    }

    sort.Slice(levelSums, func(i, j int) bool {
        return levelSums[i] > levelSums[j]
    })

    return levelSums[k-1]
}

The Go implementation mirrors the Python logic closely.

One important difference is the use of int64 for level sums. Since node values can be large and many nodes may exist on a single level, using regular int could risk overflow on some systems. Converting node values to int64 ensures correctness.

Go does not have a built in deque like Python, so the queue is implemented using a slice. Removing the front element is done with:

queue = queue[1:]

Sorting is performed using sort.Slice with a custom descending comparator.

Worked Examples

Example 1

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

Tree structure:

        5
      /   \
     8     9
    / \   / \
   2   1 3   7
  / \
 4   6

BFS Traversal

Level	Queue Before Processing	Level Sum	Queue After Processing
1	[5]	5	[8, 9]
2	[8, 9]	17	[2, 1, 3, 7]
3	[2, 1, 3, 7]	13	[4, 6]
4	[4, 6]	10	[]

Collected level sums:

[5, 17, 13, 10]

After sorting descending:

[17, 13, 10, 5]

The 2nd largest sum is:

13

Example 2

Input:
root = [1,2,null,3]
k = 1

Tree structure:

    1
   /
  2
 /
3

BFS Traversal

Level	Queue Before Processing	Level Sum	Queue After Processing
1	[1]	1	[2]
2	[2]	2	[3]
3	[3]	3	[]

Collected sums:

[1, 2, 3]

Sorted descending:

[3, 2, 1]

The 1st largest sum is:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + L log L)	BFS visits every node once, sorting level sums takes O(L log L)
Space	O(L + w)	Stores level sums and BFS queue

Here:

• n is the number of nodes
• L is the number of levels
• w is the maximum width of the tree

The BFS traversal itself is linear because each node is processed exactly once. The additional sorting cost depends only on the number of levels, which is at most n.

The queue may temporarily hold all nodes from the widest level, which determines the auxiliary space usage.

Test Cases

from collections import deque
from typing import Optional

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:
        queue = deque([root])
        level_sums = []

        while queue:
            level_size = len(queue)
            current_sum = 0

            for _ in range(level_size):
                node = queue.popleft()
                current_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            level_sums.append(current_sum)

        if len(level_sums) < k:
            return -1

        level_sums.sort(reverse=True)

        return level_sums[k - 1]

# Example 1
root1 = TreeNode(5)
root1.left = TreeNode(8)
root1.right = TreeNode(9)
root1.left.left = TreeNode(2)
root1.left.right = TreeNode(1)
root1.right.left = TreeNode(3)
root1.right.right = TreeNode(7)
root1.left.left.left = TreeNode(4)
root1.left.left.right = TreeNode(6)

assert Solution().kthLargestLevelSum(root1, 2) == 13  # provided example

# Example 2
root2 = TreeNode(1)
root2.left = TreeNode(2)
root2.left.left = TreeNode(3)

assert Solution().kthLargestLevelSum(root2, 1) == 3  # largest level sum

# Single level tree
root3 = TreeNode(10)
root3.left = TreeNode(20)

assert Solution().kthLargestLevelSum(root3, 2) == 10  # second largest level

# k larger than number of levels
root4 = TreeNode(1)
root4.left = TreeNode(2)

assert Solution().kthLargestLevelSum(root4, 5) == -1  # insufficient levels

# Duplicate level sums
root5 = TreeNode(5)
root5.left = TreeNode(2)
root5.right = TreeNode(3)
root5.left.left = TreeNode(1)
root5.right.right = TreeNode(1)

assert Solution().kthLargestLevelSum(root5, 2) == 5  # duplicate sums counted

# Skewed tree
root6 = TreeNode(1)
root6.right = TreeNode(2)
root6.right.right = TreeNode(3)
root6.right.right.right = TreeNode(4)

assert Solution().kthLargestLevelSum(root6, 3) == 2  # linked-list shaped tree

# Large values
root7 = TreeNode(1000000)
root7.left = TreeNode(1000000)
root7.right = TreeNode(1000000)

assert Solution().kthLargestLevelSum(root7, 1) == 2000000  # large sums

Test	Why
Balanced example tree	Validates normal multi-level processing
Left-skewed tree	Ensures BFS handles unbalanced trees
Two-level tree	Confirms ordering logic
k larger than levels	Verifies -1 handling
Duplicate sums	Ensures duplicates are counted
Right-skewed tree	Tests extreme imbalance
Large node values	Validates large integer handling

Edge Cases

k is larger than the number of levels

A common mistake is assuming there will always be at least k levels. If the tree contains fewer levels than requested, accessing the kth element after sorting would cause an error or incorrect result.

The implementation explicitly checks:

if len(level_sums) < k:
    return -1

This guarantees correct behavior for insufficient levels.

Highly skewed trees

A tree may degenerate into a linked list where every node has only one child. In this case, the height becomes n, and recursive depth-based approaches can become inefficient or even risk stack overflow in some languages.

The BFS implementation handles skewed trees naturally because it processes nodes iteratively with a queue.

Duplicate level sums

The problem states that sums do not need to be distinct. A buggy implementation might incorrectly remove duplicates using a set before sorting.

For example:

Level sums = [10, 5, 10]

The 2nd largest value should still be 10.

The implementation preserves every level sum in the list, ensuring duplicates are counted correctly.

Very large level sums

Since node values can be up to 10^6 and there may be many nodes on a level, the total sum can become quite large.

The Go solution uses int64 explicitly to avoid overflow issues. Python integers automatically expand as needed, so no special handling is required there.