Given the root of a binary tree, write a function to find its maximum width.
The width of a level is measured between the leftmost and rightmost non-null nodes at that level, and it counts the missing (null) nodes in between as if the tree were complete at that level. In other words, the width isn't just how many nodes are actually present on the level, it's the full span from the leftmost node to the rightmost node, gaps included.
So if a level has a node on the far left and a node on the far right but nothing between them, the width is the total number of positions spanning the two, not 2.
Return the maximum width across all levels of the tree.
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
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 positions between the right-most and left-most non-null nodes at that level. The catch that trips most people up: this counts the null nodes sitting between those two ends, as if the level were fully filled in like a complete binary tree. So a level with a node on the far left and a node on the far right but nothing in between isn't width 2 — it's the entire span between them.
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 positions of the nodes at each level are labeled in gray
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 + 1 and our right child's position is 2 * p + 2:
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 rightmost 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.
Keeping Positions Small
Positions double at every level, so on a deep tree they get huge. A tree that is just a chain of right children 70 levels deep has a node at position 270 - 2, which overflows a 64-bit integer and loses precision in JavaScript, even though that level only holds one node.
The fix is to normalize each level. When we pop a node, we subtract the position of the leftmost node on its level before using it, so the leftmost node on every level sits at position 0. Children are then numbered from that normalized position. Only the distance between positions matters for width, so this doesn't change the answer, and positions now stay below twice the width of the level above. The width of a level is then just the normalized position of the rightmost node plus one.
Solution
class Solution:
def maxWidth(self, root: TreeNode) -> List[int]:
if not root:
return 0
# enqueue the root node with position 0
queue = deque([(root, 0)])
max_ = 0
while queue:
level_size = len(queue)
# leftPos is the position of the leftmost node at the current level
_, leftPos = queue[0]
rightPos = -1
for i in range(level_size):
node, pos = queue.popleft()
# normalize against the leftmost position so positions restart at 0 each level
pos -= leftPos
# update rightPos to the position of the rightmost node
# when we reach the last node in the level
if i == level_size - 1:
rightPos = pos
# add the children to the queue with their positions
if node.left:
queue.append((node.left, 2 * pos + 1))
if node.right:
queue.append((node.right, 2 * pos + 2))
# rightPos + 1 is the width of the current level
max_ = max(max_, rightPos + 1)
return max_
Test Your Knowledge
Login to take the complexity quiz and track your progress
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.
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).
Your account is free and you can post anonymously if you choose.