 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: 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. 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 

Layer with Max Sum


-----problem-----

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.


        \b{Example:}

        \image{0, 200}

        $$
        \Large \texttt{=> returns 2}
        $$
        \b{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. 

-----solution-----


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:

\answer

\tc $O(n)$. We loop through all the nodes.

\sc $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. 





Recursion

Layer with Max Sum