Breadth-First Search
Maximum Width of Binary Tree
DESCRIPTION (inspired by 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.
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
Calculating Width
Position of Nodes
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_
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).
Mark as read
Unlock Premium Coding Content
On This Page
Your account is free and you can post anonymously if you choose.