LeetCode 662: Maximum Width of Binary Tree

Problem Restatement

We are given the root of a binary tree.

We need to return the maximum width among all levels of the tree.

The width of a level is measured between the leftmost and rightmost non-null nodes on that level.

However, null nodes between those two endpoints are also counted, as if the tree were placed inside a complete binary tree.

Input and Output

Example function shape:

def widthOfBinaryTree(root: Optional[TreeNode]) -> int:
    ...

Examples

Consider this tree:

        1
       / \
      3   2
     / \   \
    5   3   9

The third level contains:

5, 3, null, 9

The leftmost non-null node is 5.

The rightmost non-null node is 9.

The null position between 3 and 9 is counted.

So the width of that level is:

4

The answer is:

4

Another example:

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

The fourth level contains:

6, null, null, null, null, null, 7

So its width is:

7

The answer is:

7

First Thought: Count Nodes Per Level

A first idea is to run BFS and count how many real nodes appear on each level.

But this is not enough.

For example:

  5       9
 /         \
6           7

At the bottom level, there are only two real nodes: 6 and 7.

But the width is not 2.

The missing null positions between them must be counted.

So we need a way to remember where each node would appear in a complete binary tree.

Key Insight

Assign each node an index as if it were in a complete binary tree.

Use this indexing rule:

Then the width of one level is:

rightmost_index - leftmost_index + 1

This works because the index gap automatically counts missing null positions between real nodes.

Why Index Normalization Helps

If the tree is deep, complete-tree indices can become very large.

Python can handle large integers, but it is still cleaner to normalize indices at every level.

For each level, let:

base = queue[0][1]

Then subtract base from every index on that level.

This keeps indices small while preserving all differences inside the level.

For example, if a level has indices:

100, 101, 107

normalizing by 100 gives:

0, 1, 7

The width is still:

7 - 0 + 1 = 8

Algorithm

Use BFS.

Each queue entry stores:

(node, index)

Start with:

(root, 0)

For each level:

1. Let level_size be the number of nodes currently in the queue.
2. Read the first index and last index in the queue.
3. Update the answer with:

last_index - first_index + 1

4. Process every node on that level.
5. Normalize its index by subtracting the first index.
6. Push its left child with index 2 * normalized_index.
7. Push its right child with index 2 * normalized_index + 1.

Return the largest width found.

Correctness

The algorithm assigns each node the same relative position it would have in a complete binary tree.

For any level, the leftmost non-null node and rightmost non-null node have indices equal to their complete-tree positions. Every missing node between them would occupy an index between those two values.

Therefore:

rightmost_index - leftmost_index + 1

counts exactly the width required by the problem.

BFS processes the tree level by level, so when the algorithm computes a width, the queue contains exactly the non-null nodes on that level.

The algorithm updates the answer using the width of every level. Therefore, after all levels are processed, the answer is the maximum width among all levels.

Index normalization does not change widths because subtracting the same base from every index on one level preserves all index differences.

Thus, the algorithm returns the correct maximum width.

Complexity

Here, n is the number of nodes, and w is the maximum number of real nodes stored in the queue at any level.

Implementation

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        answer = 0
        queue = deque([(root, 0)])

        while queue:
            level_size = len(queue)
            first_index = queue[0][1]
            last_index = queue[-1][1]

            answer = max(answer, last_index - first_index + 1)

            for _ in range(level_size):
                node, index = queue.popleft()
                index -= first_index

                if node.left is not None:
                    queue.append((node.left, 2 * index))

                if node.right is not None:
                    queue.append((node.right, 2 * index + 1))

        return answer

Code Explanation

We handle an empty tree first:

if root is None:
    return 0

Then we start BFS:

queue = deque([(root, 0)])

Each queue item contains a node and its complete-tree index.

At the start of each level, the queue contains exactly the nodes on that level.

level_size = len(queue)
first_index = queue[0][1]
last_index = queue[-1][1]

The current level width is:

last_index - first_index + 1

So we update the answer:

answer = max(answer, last_index - first_index + 1)

Then we process all nodes on this level.

for _ in range(level_size):

We normalize the index:

index -= first_index

This keeps child indices small.

For the left child:

queue.append((node.left, 2 * index))

For the right child:

queue.append((node.right, 2 * index + 1))

Finally, after all levels are processed:

return answer

Testing

def run_tests():
    s = Solution()

    # Tree:
    #         1
    #        / \
    #       3   2
    #      / \   \
    #     5   3   9
    root = TreeNode(1)
    root.left = TreeNode(3, TreeNode(5), TreeNode(3))
    root.right = TreeNode(2, None, TreeNode(9))

    assert s.widthOfBinaryTree(root) == 4

    # Tree:
    #         1
    #        / \
    #       3   2
    #      /     \
    #     5       9
    #    /         \
    #   6           7
    root = TreeNode(1)
    root.left = TreeNode(3, TreeNode(5), None)
    root.right = TreeNode(2, None, TreeNode(9))
    root.left.left.left = TreeNode(6)
    root.right.right.right = TreeNode(7)

    assert s.widthOfBinaryTree(root) == 7

    # Single node.
    root = TreeNode(1)

    assert s.widthOfBinaryTree(root) == 1

    # Skewed tree.
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.right = TreeNode(3)

    assert s.widthOfBinaryTree(root) == 1

    print("all tests passed")

run_tests()

Test meaning: