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.
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 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 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() # 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)) if node.right: queue.append((node.right, 2 * pos + 1)) # rightPos - leftPos + 1 is the width of the current level max_ = max(max_, rightPos - leftPos + 1) return max_
class Solution { public int maxWidth(TreeNode root) { if (root == null) { return 0; } // enqueue the root node with position 0 Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>(); queue.offer(new Pair<>(root, 0)); int maxWidth = 0; while (!queue.isEmpty()) { int levelSize = queue.size(); // leftPos is the position of the leftmost node at the current level int leftPos = queue.peek().getValue(); int rightPos = -1; for (int i = 0; i < levelSize; i++) { Pair<TreeNode, Integer> current = queue.poll(); TreeNode node = current.getKey(); int pos = current.getValue(); // update rightPos to the position of the rightmost node // when we reach the last node in the level if (i == levelSize - 1) { rightPos = pos; } // add the children to the queue with their positions if (node.left != null) { queue.offer(new Pair<>(node.left, 2 * pos)); } if (node.right != null) { queue.offer(new Pair<>(node.right, 2 * pos + 1)); } } // rightPos - leftPos + 1 is the width of the current level maxWidth = Math.max(maxWidth, rightPos - leftPos + 1); } return maxWidth; }}
type NodePosition struct { Node *TreeNode Pos int}func maxWidth(root *TreeNode) int { if root == nil { return 0 } // enqueue the root node with position 0 queue := []NodePosition{{root, 0}} maxWidth := 0 for len(queue) > 0 { levelSize := len(queue) // leftPos is the position of the leftmost node at the current level leftPos := queue[0].Pos rightPos := -1 for i := 0; i < levelSize; i++ { current := queue[0] queue = queue[1:] node, pos := current.Node, current.Pos // update rightPos to the position of the rightmost node // when we reach the last node in the level if i == levelSize-1 { rightPos = pos } // add the children to the queue with their positions if node.Left != nil { queue = append(queue, NodePosition{node.Left, 2 * pos}) } if node.Right != nil { queue = append(queue, NodePosition{node.Right, 2*pos + 1}) } } // rightPos - leftPos + 1 is the width of the current level if rightPos-leftPos+1 > maxWidth { maxWidth = rightPos - leftPos + 1 } } return maxWidth}
class Solution { maxWidth(root: TreeNode | null): number { if (!root) { return 0; } // enqueue the root node with position 0 const queue: [TreeNode, number][] = [[root, 0]]; let maxWidth = 0; while (queue.length > 0) { const levelSize = queue.length; // leftPos is the position of the leftmost node at the current level const leftPos = queue[0][1]; let rightPos = -1; for (let i = 0; i < levelSize; i++) { const [node, pos] = queue.shift()!; // update rightPos to the position of the rightmost node // when we reach the last node in the level if (i === levelSize - 1) { rightPos = pos; } // add the children to the queue with their positions if (node.left) { queue.push([node.left, 2 * pos]); } if (node.right) { queue.push([node.right, 2 * pos + 1]); } } // rightPos - leftPos + 1 is the width of the current level maxWidth = Math.max(maxWidth, rightPos - leftPos + 1); } return maxWidth; }}
