 Given the root node of a binary tree `root`, return the maximum width on any layer, assuming the tree is physically laid out in the shape of a perfect tree. Example: We need to compute the width of each layer in the tree. We'll use a BFS here, since a BFS goes layer-by-layer naturally. Here's the code for a BFS: ``` queue = deque([root]) while queue: iterate through the next layer for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.appen

Max Perfect Width of a Tree



-----problem-----


Given the root node of a binary tree `root`, return the maximum width on any layer, assuming the tree is physically laid out in the shape of a perfect tree.



\b{Example:}
\image{0}

$$\large \texttt{=> returns 10}$$

-----solution-----

We need to compute the width of each layer in the tree. We'll use a BFS here, since a BFS goes layer-by-layer naturally. Here's the code for a BFS:


```
queue = deque([root])
while queue:
    # iterate through the next layer
    for _ in range(len(queue)):
        node = queue.popleft()
        if node.left:  queue.append(node.left)
        if node.right: queue.append(node.right)
```


We can use a BFS to find the width of a layer, by labeling all the nodes with a number (see below). The width is the rightmost number minus the leftmost number, plus 1:

\image{1}

The numbers are always 0, 1, 2, ... like this:
\image{2}

In order to keep track of which node gets which number, the trick is to get the numbers in the next layer from the numbers in the previous layer. You get the left child's number by multiplying by 2. And you get the right child's number by multiplying by 2, and adding 1. Here's this drawn visually:

\image{3, 180}




Now, we can modify our BFS code so that each node gets a number.
Inside the queue, we'll just store each node's number along with the node itself.



```
queue = deque([(root, 0)]) # (node, number)
while queue:
    for _ in range(len(queue)):
        # now we have access to the number
        node, n = queue.popleft()

        if node.left:  queue.append((node.left, 2*n))
        if node.right: queue.append((node.right, 2*n + 1))
```


We can finally compute the width of each layer - we just have to find the leftmost and rightmost nodes and subtract their numbers. This is actually really easy, because the BFS visits nodes from left to right, so the leftmost node in a layer is `queue[0]`, and the rightmost node is `queue[-1]`. We talked about this in detail in the last problem.


Here's how you code this up:

\answer


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

\sc $O(n)$. The queue stores $O(n)$ nodes.


Recursion

Max Perfect Width of a Tree