⚡Flashcard Drill➔
NeetCode #428LC-2583MediumTrees
← Back to All Problems

#428 · #2583 · Kth Largest Sum in a Binary Tree(二叉树中的第 K 大层和)

📌 Problem Statement & Constraints

You are given the root of a binary tree and a positive integer k. Return the k-th largest level sum (the sum of node values at each level), or -1 if there are fewer than k levels. Constraints: the number of nodes is in [1, 10^5], 1 <= Node.val <= 10^6, 1 <= k <= 10^5.

💡 Core Algorithmic Approaches

  1. A BFS with a frozen level size collects each level's sum.
  2. Then sort the sums descending and index the k-th.
  3. If k exceeds the number of levels, return -1.
  4. A min-heap of size k avoids the full sort, but at these limits the sort is simpler.

💻 Benchmark Python3 Implementation

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        from collections import deque
        q = deque([root])
        sums = []
        while q:
            n = len(q)
            s = 0
            for _ in range(n):
                node = q.popleft()
                s += node.val
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            sums.append(s)                 # one entry per level
        if k > len(sums):
            return -1
        sums.sort(reverse=True)
        return sums[k - 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + L log L) where L is the number of levels: the BFS is linear and the sort is over the levels.
💾 Space Complexity
O(w) for the widest level plus O(L) for the sums.

⚠️ Interview Pitfalls & Follow-ups

  • Using k as a 0-indexed position: the problem is 1-indexed, hence sums[k - 1].
  • Forgetting the k > L case: the answer is -1.
  • Summing the whole tree: the sums are per level.
  • Using a DFS without tracking depth: the level grouping would be lost.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems