Problem Description

You are given the root of a binary tree. Your task is to find the maximum width of the tree.

The width of a tree level is measured as the distance between the leftmost and rightmost non-null nodes at that level, plus 1. When calculating this distance, you must also count any null nodes that would exist between these endpoints if the tree were a complete binary tree at that level.

The maximum width is the largest width value among all levels in the tree.

For example, consider a tree where level 3 has nodes at positions that would be indices 2 and 7 in a complete binary tree. The width would be 7 - 2 + 1 = 6, even if there are null nodes in positions 3, 4, 5, and 6.

The solution uses a level-order traversal (BFS) approach with a queue. Each node is paired with its position index as if it were in a complete binary tree:

• The root starts at position 1
• For any node at position i, its left child is at position 2*i (achieved by i << 1)
• Its right child is at position 2*i + 1 (achieved by i << 1 | 1)

During the traversal, for each level, the width is calculated as rightmost_position - leftmost_position + 1. The algorithm keeps track of the maximum width seen across all levels and returns it as the final answer.

The answer is guaranteed to fit within a 32-bit signed integer.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure.

DFS

• Following the flowchart, when we have a tree structure, the natural conclusion is to use DFS (Depth-First Search).

Conclusion: The flowchart suggests using a DFS approach for this binary tree problem.

However, it's worth noting that while the flowchart leads us to DFS, the actual solution provided uses BFS (Breadth-First Search) with a queue. This is because the problem requires us to process the tree level by level to calculate the width at each level. BFS is more natural for level-order traversal since it processes all nodes at the same depth before moving to the next level.

The DFS pattern could also solve this problem by tracking the leftmost and rightmost positions at each depth using recursion, but BFS provides a more straightforward implementation for this particular width calculation problem where we need to examine nodes level by level.

Intuition

The key insight is to treat the binary tree as if it were a complete binary tree and assign position indices to each node. Think of it like numbering seats in a theater where every row has twice as many seats as the previous row, even if some seats are empty.

When we number nodes in a complete binary tree starting from 1 at the root:

• Every left child gets position 2 * parent_position
• Every right child gets position 2 * parent_position + 1

This numbering system naturally captures the "distance" between nodes. If we have two nodes at the same level with positions i and j, the width between them is j - i + 1, which accounts for all positions (including empty ones) between them.

Why does this work? Consider two nodes at the same level - one far to the left and one far to the right. Their position numbers will reflect how many "empty spots" exist between them because each missing node still increments the position counter in our numbering scheme.

For example, if at level 3 we only have nodes at what would be positions 2 and 7 in a complete tree, we know there are 5 positions between them (positions 3, 4, 5, 6 are empty), giving us a width of 7 - 2 + 1 = 6.

We need to examine every level to find which one has the maximum width. BFS is perfect for this because it naturally processes nodes level by level. At each level, we can easily identify the leftmost position (first in queue) and rightmost position (last in queue) to calculate that level's width.

The bit manipulation (i << 1 for 2*i and i << 1 | 1 for 2*i + 1) is just an efficient way to compute the child positions, but the core idea remains the same: we're simulating position indices in a complete binary tree to measure distances.

Learn more about Tree, Depth-First Search, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a level-order traversal (BFS) using a queue to track nodes along with their position indices.

Data Structure Setup:

• We use a deque (double-ended queue) to store pairs: (node, position_index)
• Initialize the queue with the root node at position 1: q = deque([(root, 1)])
• Track the maximum width seen so far in variable ans

Algorithm Steps:

1. Process each level: While the queue is not empty, we process all nodes at the current level.

2. Calculate width for current level: Before processing nodes, calculate the width using the positions of the first and last nodes in the queue:

   ans = max(ans, q[-1][1] - q[0][1] + 1)

   • q[0][1] gives the position of the leftmost node
   • q[-1][1] gives the position of the rightmost node
   • The width is rightmost - leftmost + 1

3. Process all nodes at current level: Use a for loop with range(len(q)) to ensure we only process nodes from the current level:

   for _ in range(len(q)):
       root, i = q.popleft()

4. Add children with calculated positions: For each node, add its children to the queue with their computed positions:

   • Left child position: i << 1 (equivalent to 2 * i)
   • Right child position: i << 1 | 1 (equivalent to 2 * i + 1)

   if root.left:
       q.append((root.left, i << 1))
   if root.right:
       q.append((root.right, i << 1 | 1))

5. Return result: After processing all levels, return the maximum width found.

Why this works:

• By assigning positions as if nodes were in a complete binary tree, we preserve the spatial relationship between nodes
• The BFS ensures we process complete levels before moving to the next
• The position difference accurately captures the width including null nodes between the endpoints
• Using bit operations (<< and |) provides efficient position calculations

The time complexity is O(n) where n is the number of nodes, as we visit each node once. The space complexity is O(w) where w is the maximum width of the tree (the maximum number of nodes in any level).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this binary tree:

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

Initial Setup:

• Queue: [(node_1, 1)]
• Maximum width: 0

Level 1 (Root):

• Queue has 1 element: [(node_1, 1)]
• Width calculation: 1 - 1 + 1 = 1
• Update max width to 1
• Process node_1 at position 1:
  • Add left child (node_3) at position 1 << 1 = 2
  • Add right child (node_2) at position 1 << 1 | 1 = 3
• Queue after level: [(node_3, 2), (node_2, 3)]

Level 2:

• Queue has 2 elements: [(node_3, 2), (node_2, 3)]
• Width calculation: 3 - 2 + 1 = 2
• Update max width to 2
• Process node_3 at position 2:
  • Add left child (node_5) at position 2 << 1 = 4
  • No right child
• Process node_2 at position 3:
  • No left child
  • Add right child (node_9) at position 3 << 1 | 1 = 7
• Queue after level: [(node_5, 4), (node_9, 7)]

Level 3:

• Queue has 2 elements: [(node_5, 4), (node_9, 7)]
• Width calculation: 7 - 4 + 1 = 4
• Update max width to 4
• Note: Even though we only have 2 actual nodes, the width is 4 because positions 5 and 6 would exist between them in a complete tree
• Process node_5 at position 4:
  • Add left child (node_6) at position 4 << 1 = 8
  • No right child
• Process node_9 at position 7:
  • No left child
  • Add right child (node_7) at position 7 << 1 | 1 = 15
• Queue after level: [(node_6, 8), (node_7, 15)]

Level 4:

• Queue has 2 elements: [(node_6, 8), (node_7, 15)]
• Width calculation: 15 - 8 + 1 = 8
• Update max width to 8
• Process both nodes (they have no children)
• Queue becomes empty

Result: The maximum width is 8 (found at level 4).

The key insight is how position indices capture the "spread" of nodes. At level 4, node_6 is at position 8 (far left subtree) and node_7 is at position 15 (far right subtree). The width of 8 accounts for all the missing nodes that would exist between them in a complete binary tree.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree. The algorithm uses BFS (Breadth-First Search) to traverse the tree level by level. Each node is visited exactly once - we add it to the queue once and remove it once. The operations inside the loop (max comparison, append, popleft) are all O(1) operations. Therefore, the overall time complexity is linear with respect to the number of nodes.

Space Complexity: O(w) where w is the maximum width of the tree. The space complexity is determined by the queue that stores nodes at each level. In the worst case, the queue will contain all nodes at the widest level of the tree. For a complete binary tree, this could be up to n/2 nodes at the last level, making it O(n) in the worst case. However, more precisely, the space complexity is bounded by the maximum number of nodes that can exist at any single level, which is the width of the tree.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Position Indices

The most critical pitfall in this solution is integer overflow when dealing with deep or skewed trees. As we traverse deeper levels, the position indices grow exponentially (doubling at each level). For a skewed tree of depth d, the position index can reach 2^d, which quickly exceeds integer limits.

Example scenario:

• A left-skewed tree with 100 levels would have the rightmost node at position 2^100
• This far exceeds even 64-bit integer limits

Solution - Position Normalization: Normalize positions at each level by subtracting the leftmost position from all positions in that level. This keeps the relative distances the same while preventing overflow:

def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
    max_width = 0
    queue = deque([(root, 0)])  # Start with position 0
  
    while queue:
        # Calculate width before normalization
        current_level_width = queue[-1][1] - queue[0][1] + 1
        max_width = max(max_width, current_level_width)
      
        # Get the leftmost position for normalization
        left_most = queue[0][1]
      
        level_size = len(queue)
        for _ in range(level_size):
            node, position = queue.popleft()
          
            # Normalize position relative to leftmost node
            normalized_pos = position - left_most
          
            # Add children with normalized positions
            if node.left:
                queue.append((node.left, normalized_pos * 2))
            if node.right:
                queue.append((node.right, normalized_pos * 2 + 1))
  
    return max_width

2. Not Processing Levels Completely

Another common mistake is forgetting to capture the queue length before the loop, leading to processing nodes from multiple levels together:

# WRONG - processes nodes from different levels
while queue:
    for node, pos in queue:  # This iterates over a changing queue!
        # Process node...

# CORRECT - processes one level at a time
while queue:
    level_size = len(queue)  # Capture size before loop
    for _ in range(level_size):
        node, pos = queue.popleft()
        # Process node...

3. Using Wrong Position Formula

Mixing up the position calculation formulas or using 0-based vs 1-based indexing inconsistently:

# If using 0-based indexing:
left_child_pos = parent_pos * 2
right_child_pos = parent_pos * 2 + 1

# If using 1-based indexing:
left_child_pos = parent_pos * 2
right_child_pos = parent_pos * 2 + 1

# Common mistake: mixing conventions
# Starting with 1 but using 0-based formulas would give wrong results

The key is to be consistent throughout the implementation and ensure the width calculation formula matches the indexing scheme used.