2583. Kth Largest Sum in a Binary Tree

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:

• The number of nodes in the tree is n.
• 2 <= n <= 105
• 1 <= Node.val <= 106
• 1 <= k <= n

Approach 01:

#include <vector>
#include <algorithm>
#include <functional>

class Solution {
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        std::vector<long> levelSumList;
        calculateLevelSums(root, 0, levelSumList);
        if (levelSumList.size() < k)
            return -1;

        std::nth_element(levelSumList.begin(), levelSumList.begin() + k - 1, levelSumList.end(), std::greater<>());
        return levelSumList[k - 1];
    }

private:
    void calculateLevelSums(TreeNode* node, int currentLevel, std::vector<long>& levelSumList) {
        if (node == nullptr)
            return;
        if (levelSumList.size() == currentLevel)
            levelSumList.push_back(0);
        levelSumList[currentLevel] += node->val;
        calculateLevelSums(node->left, currentLevel + 1, levelSumList);
        calculateLevelSums(node->right, currentLevel + 1, levelSumList);
    }
};

class Solution:
    def kthLargestLevelSum(self, root: Optional[TreeNode], k: int) -> int:
        levelSumList = []
        self.calculateLevelSums(root, 0, levelSumList)
        if len(levelSumList) < k:
            return -1

        # Find the k-th largest element using n-th element logic
        levelSumList.sort(reverse=True)
        return levelSumList[k - 1]

    def calculateLevelSums(self, node: TreeNode, currentLevel: int, levelSumList: list[int]) -> None:
        if node is None:
            return
        if len(levelSumList) == currentLevel:
            levelSumList.append(0)
        levelSumList[currentLevel] += node.val
        self.calculateLevelSums(node.left, currentLevel + 1, levelSumList)
        self.calculateLevelSums(node.right, currentLevel + 1, levelSumList)

Time Complexity

• Tree Traversal (Level Sum Calculation):

  The function performs a depth-first traversal (DFS) of the tree to calculate the sum of values at each level. Each node is visited once, so the time complexity for this step is \(O(n)\), where n is the total number of nodes in the tree.

• Finding the K-th Largest Element:

  After calculating the level sums, we use std::nth_element to find the K-th largest sum. This operation runs in \(O(L)\), where L is the number of levels in the tree, since nth_element works in linear time relative to the size of the input.

• Overall Time Complexity:

  The overall time complexity is \(O(n + L)\), which simplifies to \(O(n)\) since \(L\) (the number of levels) is typically much smaller than \(n\).

Space Complexity

• Space for Level Sums:

  We store the sum of node values for each level in a vector. The number of levels in a binary tree is at most \(O(\log n)\) for a balanced tree and \(O(n)\) in the worst case (for a skewed tree), so the space required for the level sums is \(O(L)\), where \(L\) is the number of levels.

• Recursive Call Stack:

  The depth of the recursive call stack for the DFS is proportional to the height of the tree, which is \(O(\log n)\) for a balanced tree and \(O(n)\) for a skewed tree.

• Overall Space Complexity:

  The overall space complexity is \(O(n)\) in the worst case due to both the level sum vector and the recursive call stack.