Recursion

Layer with Max Sum

Given the root of a binary tree root, determine which layer has the largest sum, and return its layer number.

Layers are indexed at 1. If there are multiple solutions for a given tree, you can return any one of the solutions.

Example:

\notag \Large \texttt{=> returns 2}

Explanation: Layer number 2 has the highest sum of five, so we return 2. Layer 1 has a sum of one, and Layer 3 has a sum of zero.

First Few Test Cases:

layerMaxSum(TreeNode.of([1, 2, 3, 4, 5, None, -9]))
# 2

layerMaxSum(TreeNode.of([1]))
# 1

layerMaxSum(TreeNode.of([-1]))
# 1

We should use a BFS, since we need to compute the sum over each layer. Here's the code for a BFS:

from collections import deque

queue = deque([root])
while queue:
    # loop through nodes in current layer
    for _ in range(len(queue)):
        node = queue.popleft()
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

To solve this problem, we need to keep track of the maximum sum over any layer we've seen so far, maxSum. We also need to return the layer that has the maximum sum, bestLayer. This requires that we keep track of which layer we're on currLayer.

Here's how you modify the above BFS to do this:

from collections import deque

def layerMaxSum(root):
    currLayer = 1                       # initialize variables
    bestLayer = None
    maxSum = float('-inf')

    queue = deque([root])
    while queue:
        layerSum = 0                    # initialize sum
        for _ in range(len(queue)):
            node = queue.popleft()
            layerSum += node.val        # add to the sum
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
            
        if layerSum > maxSum:           # update variables
            maxSum = layerSum
            bestLayer = currLayer
        currLayer += 1

    return bestLayer

Time Complexity $O(n)$ . We loop through all the nodes.

Space Complexity $O(n)$ . The queue might contain all the nodes, so it uses $O(n)$ memory. We store 3 variables, which is $O(3) = O(1)$ memory. This is a total of $O(1) + O(n) = O(n)$ memory.

Mark as Completed:

Submits:

layerMaxSum

Imports:

TreeNode

Test your code to get an output here!

layerMaxSum(

)

Test your code to get an output here!