Problem statement

You are given the root of a binary tree and a positive integer k.

The level sum of a level is the sum of the values of all the nodes on that level (nodes at the same distance from the root).

Return the k-th largest level sum (sums are not necessarily distinct; equal sums count separately). If the tree has fewer than k levels, return -1.

Example 1

Input: root = [5,8,9,2,1,3,7,4,6], k = 2
Output: 13
Explanation: The level sums are 5, 17, 13 and 10. In decreasing order: 17, 13, 10, 5 — the second is 13.

Example 2

Input: root = [1,2,null,3], k = 1
Output: 3
Explanation: The level sums are 1, 2 and 3; the largest is 3.

Example 3

Input: root = [4,2,6], k = 3
Output: -1
Explanation: The tree has only two levels, so there is no third largest sum.

Constraints

• 2 <= number of nodes <= 10^5
• 1 <= Node.val <= 10^4 (LeetCode allows 10^6; reduced here so every level sum fits in a 32-bit integer)
• 1 <= k <= number of nodes

Hints for Kth Largest Sum in a Binary Tree

1. Hint 1

   First compute every level's sum — a breadth-first walk that processes one level at a time does it in one pass.

2. Hint 2

   There are at most as many levels as nodes, so sorting the sums is cheap.

3. Hint 3

   Check the number of levels before indexing: when it is below k the answer is -1.

How to solve Kth Largest Sum in a Binary Tree

A level-by-level breadth-first traversal yields each level's sum; sort the sums in decreasing order and read position k - 1.

Approach

1. Start with the root as the only node of the current level.
2. Add up the current level's values into one sum and collect the children as the next level; repeat until no level is left.
3. If fewer than k sums were produced, return -1.
4. Otherwise sort the sums in decreasing order and return the k-th one.

Why it works

The breadth-first walk visits every node exactly once and groups nodes by depth, so each sum is exactly one level's total. Sorting puts them in decreasing order, and equal sums stay as separate entries, which is what the ranking asks for.

Complexity

• Time — O(n + L log L), L the number of levels
• Space — O(n) for the queue and the sums

Pitfalls

• Equal sums are not merged — two levels both summing to 10 are the first and second largest if nothing is bigger.
• On LeetCode the sums need 64-bit integers; here the values are capped so 32 bits suffice, but the levels must still be summed completely.

Reference solution

Python

from typing import Optional

def kthLargestLevelSum(root: Optional[TreeNode], k: int) -> int:
    sums = []
    level = [root] if root else []
    while level:
        sums.append(sum(node.val for node in level))
        nxt = []
        for node in level:
            if node.left:
                nxt.append(node.left)
            if node.right:
                nxt.append(node.right)
        level = nxt
    if len(sums) < k:
        return -1
    sums.sort(reverse=True)
    return sums[k - 1]

Java

public static int kthLargestLevelSum(TreeNode root, int k) {
    List<Integer> sums = new ArrayList<>();
    List<TreeNode> level = new ArrayList<>();
    if (root != null) level.add(root);
    while (!level.isEmpty()) {
        int s = 0;
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : level) {
            s += node.val;
            if (node.left != null) next.add(node.left);
            if (node.right != null) next.add(node.right);
        }
        sums.add(s);
        level = next;
    }
    if (sums.size() < k) return -1;
    sums.sort(Collections.reverseOrder());
    return sums.get(k - 1);
}

C++

int kthLargestLevelSum(TreeNode* root, int k) {
    vector<int> sums;
    vector<TreeNode*> level;
    if (root) level.push_back(root);
    while (!level.empty()) {
        int s = 0;
        vector<TreeNode*> next;
        for (TreeNode* node : level) {
            s += node->val;
            if (node->left) next.push_back(node->left);
            if (node->right) next.push_back(node->right);
        }
        sums.push_back(s);
        level = next;
    }
    if ((int) sums.size() < k) return -1;
    sort(sums.rbegin(), sums.rend());
    return sums[k - 1];
}

JavaScript

var kthLargestLevelSum = function(root, k) {
    var sums = [];
    var level = root === null ? [] : [root];
    while (level.length > 0) {
        var s = 0, next = [];
        for (var i = 0; i < level.length; i++) {
            var node = level[i];
            s += node.val;
            if (node.left !== null) next.push(node.left);
            if (node.right !== null) next.push(node.right);
        }
        sums.push(s);
        level = next;
    }
    if (sums.length < k) return -1;
    sums.sort(function(a, b) { return b - a; });
    return sums[k - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Convert Sorted List to Binary Search Tree Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Duplicate Subtree in Binary Tree Medium