Problem Statement in English

You’re given the root of a binary tree. You need to write a function that returns the smallest level with the maximum sum of node values.

The important point to understand here is that they have essentially given us a tie breaker condition - when there are 2 levels with the same path sum, pick the smaller level.

Approach

It’s a classic level order traversal problem with a minor add-on to keep track of sum of nodes on the level.

Solution in Python


class Solution:
    def maxLevelSum(self, root: Optional[TreeNode]) -> int:
        temp = [root]

        bestSum = float("-inf")
        bestLevel = 0

        level = 0

        while temp:
            q = deque(temp)
            temp = []
            s = 0
            level+=1

            while q:
                node = q.popleft()
                s+=node.val

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

            if s > bestSum:
                bestSum = s
                bestLevel = level

        return bestLevel

Complexity

  • Time: $O(n)$
    Since we iterate over all the nodes in the tree once.

  • Space: $O(n)$
    Since we use a queue to store the nodes at each level.

And we are done.