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:

The numbers are always 0, 1, 2, ... like this:

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:

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:

from collections import deque

def maximumWidth(root):
    # keep track of max width
    maxWidth = -float('inf')

    queue = deque([(root, 0)]) # (node, number)
    while queue:
        # find the leftmost and rightmost numbers in this layer, and compute the width
        _, nL = queue[0]
        _, nR = queue[-1]
        width = nR - nL + 1
        # update the max width we've seen
        maxWidth = max(maxWidth, width)

        # visit the next layer
        for _ in range(len(queue)):
            node, n = queue.popleft()
            if node.left:  queue.append((node.left, 2*n))
            if node.right: queue.append((node.right, 2*n + 1))

    return maxWidth

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

Space Complexity $O(n)$. The queue stores $O(n)$ nodes.