## Maximum Width of Binary Tree

###### DESCRIPTION (credit Leetcode.com)

Given the root of a binary tree, write a function to find its maximum width. Each level of the binary tree has a width, which is the number of nodes between the leftmost and rightmost nodes at that level, including the null nodes between them. The function should return the maximum width of the binary tree.

###### EXAMPLES

**Example 1**:

Input:

`[4, 2, 7, 1, null, null, 9]`

Output: 4

**Example 2**:

Input:

`[4, 2, 7, 1]`

Output: 2

The third level only has one node, which means the width of that level is one.

**Example 3**:

Input:

`[4,2,7,1,null,6,9,7,null,null,1,1,null]`

Output: 7

Run your code to see results here

## Explanation

Since width is something that is calculated at each level of the binary tree, we should recognize that a level-order breadth-first traversal of the binary tree is the most straightforward way to solve this problem. If we calculate the width at each level, then the max width is just the largest of those values.

#### Calculating Width

Let's now breakdown how to calculate the width at each level of the binary tree. The width at each level is the number of nodes between the right-most and left-most nodes at that level.

#### Position of Nodes

In order to calculate the width at each level, we need to assign each node a "position" value, which represents the position of the node at that level (starting at 0). The diagram below labels the positions of each node in a binary tree:

The key insight here is that if we know the position of our node, then we can also calculate the position of both of our children. If our position is p, then our left child's position is 2 * p and our right child's position is 2 * p + 1:

With this in mind, we can extend BFS to also keep track of each node's position. Each time we add a node to the queue, we'll also add its position. Then, each time we pop a node from the queue, we'll have its position, which we can use to calculate the positions of its children, which get added to the queue.

Then, the width at each level is the position of the node minus the position of the leftmost node plus one. The rightmost node is the last node in the queue at each level, and the leftmost node is the first node in the queue at each level.

class Solution:def maxWidth(self, root: TreeNode) -> List[int]:if not root:return 0# enqueue the root node with position 0queue = deque([(root, 0)])max_ = 0while queue:level_size = len(queue)# leftPos is the position of the leftmost node at the current level_, leftPos = queue[0]rightPos = -1for i in range(level_size):node, pos = queue.popleft()# update rightPos to the position of the rightmost node# when we reach the last node in the levelif i == level_size - 1:rightPos = pos# add the children to the queue with their positionsif node.left:queue.append((node.left, 2 * pos))if node.right:queue.append((node.right, 2 * pos + 1))# rightPos - leftPos + 1 is the width of the current levelmax_ = max(max_, rightPos - leftPos + 1)return max_

## Complexity Analysis

**Time Complexity:** O(N) where N is the number of nodes in the tree. We visit each node exactly once, and each node, we perform a constant amount of work, so the time complexity is O(N).
**Space Complexity:** O(N). In the worst case, the BFS queue will contain N / 2 nodes at the last level of the tree, so the space complexity is O(N).

Loading comments...