Problem

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Examples

Example 1:

1
2
3
4
5

	   1
	 /   \
    3     2
   / \     \
  5   3     9

1
2
3

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

1
2
3
4
5
6
7

        1
       / \
      3   2
     /     \
   5        9
  /        /
6         7

1
2
3

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

1
2
3
4
5

	   1
	 /   \
    3     2
   / 
  5  

1
2
3

Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).

Solution

Method 1 - BFS

To solve the problem, we can use a Breadth-First Search (BFS) traversal, where we track the leftmost and rightmost positions of nodes at each level using a position index. This helps calculate the width of each level based on the difference between the positions of the leftmost and rightmost nodes. The maximum width of the tree is simply the maximum width among all levels.

Steps

  1. Use a Queue: During BFS, keep track of both the nodes and their respective indices. This index simulates the position in a complete binary tree representation.
  2. Track Level Bounds: For each level, note the indices of the leftmost and rightmost nodes.
  3. Calculate Width: For each level, calculate the width as rightmost index - leftmost index + 1.
  4. Update Maximum Width: Track the maximum width across all levels.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
    static class NodeInfo {
        TreeNode node;
        int pos;

        NodeInfo(TreeNode n, int p) {
            this.node = n;
            this.pos = p;
        }
    }

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        Queue<NodeInfo> q = new LinkedList<>();
        q.add(new NodeInfo(root, 0));
        int ans = 0;

        while (!q.isEmpty()) {
            int size = q.size();
            int left = q.peek().pos, right = left;

            for (int i = 0; i < size; i++) {
                NodeInfo curr = q.poll();
                right = curr.pos;

                if (curr.node.left != null) {
                    q.add(new NodeInfo(curr.node.left, 2 * curr.pos));
                }
                if (curr.node.right != null) {
                    q.add(new NodeInfo(curr.node.right, 2 * curr.pos + 1));
                }
            }

            ans = Math.max(ans, right - left + 1);
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        q: deque[tuple[TreeNode, int]] = deque([(root, 0)])
        ans: int = 0
        
        while q:
            size = len(q)
            left = q[0][1]
            right = left
            
            for _ in range(size):
                node, pos = q.popleft()
                right = pos
                
                if node.left:
                    q.append((node.left, 2 * pos))
                if node.right:
                    q.append((node.right, 2 * pos + 1))
            
            ans = max(ans, right - left + 1)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n). We visit every node once during BFS, where n is the number of nodes in the tree.
  • 🧺 Space complexity: O(n). In the worst case (i.e., a complete binary tree), the queue will hold approximately n/2 nodes at the last level.