Problem Statement in English

You’re given the root of a binary tree and an integer k. The level sum of a level is defined as the sum of all the values of the nodes at that level. Return the kth largest level sum in the binary tree. If there are fewer than k levels in the tree, return -1.


Approach

We can break this down into 2 subproblems:

  • Calculate the level sums: We can perform a level order traversal of the binary tree using a queue. For each level, we calculate the sum of the node values and store it in a list.

  • Find the kth largest level sum: Once we have the list of level sums, we can sort it in descending order and return the kth element. If k is greater than the number of levels, we return -1.

And we’re done!


Solution in Python


class Solution:
    def kthLargestLevelSum(self, root: TreeNode | None, k: int) -> int:
        def levelSums(node):
            if not node: return []

            q = deque([node])
            res = []

            while q:
                next_q = []
                levelSum = 0

                while q:
                    temp = q.popleft()
                    levelSum += temp.val

                    if temp.left:
                        next_q.append(temp.left)
                    if temp.right:
                        next_q.append(temp.right)

                res.append(levelSum)
                q = deque(next_q)
            return res

        if not root: return -1 
         
        res = levelSums(root)
        
        if k > len(res): return -1

        res.sort()
        return res[-k]

Complexity

  • Time: $O(n + h \log h)$
    where $n$ is the number of nodes in the binary tree and $h$ is the height of the binary tree.

    This is because we need to traverse all the nodes in the binary tree to calculate the level sums, which takes $O(n)$ time. After that, we sort the level sums, which takes $O(h \log h)$ time, where $h$ is the number of levels in the binary tree.

  • Space: $O(h)$
    Since we are using a queue to perform a level order traversal of the binary tree, the maximum number of nodes that can be stored in the queue at any given time is equal to the maximum number of nodes at any level of the binary tree, which is $O(h)$.


And we are done.