Introduction

The width of a binary tree can mean two slightly different things depending on the problem statement. In basic data structure discussions, it often means the maximum number of actual nodes on any level. In interview problems such as LeetCode 662, width usually includes the gaps between the leftmost and rightmost non-null positions on a level.

That second definition is the more interesting one algorithmically. It requires tracking where nodes would appear in a complete binary tree, not just counting how many nodes exist on each level.

Simple Level Width Versus Indexed Width

If you only want the number of nodes on the busiest level, a plain breadth-first traversal is enough. For each level, count how many nodes are in the queue and track the maximum.

1from collections import deque
2
3class Node:
4    def __init__(self, val, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9def max_node_count_width(root):
10    if not root:
11        return 0
12
13    queue = deque([root])
14    best = 0
15
16    while queue:
17        level_size = len(queue)
18        best = max(best, level_size)
19
20        for _ in range(level_size):
21            node = queue.popleft()
22            if node.left:
23                queue.append(node.left)
24            if node.right:
25                queue.append(node.right)
26
27    return best

That solution is correct for the simple definition, but it is not correct for the indexed definition that includes gaps.

BFS With Position Indexes

For the indexed definition, assign each node the position it would have in a complete binary tree. A common convention is:

• root gets index 0
• left child gets 2 * i
• right child gets 2 * i + 1

Then the width of a level is rightmost_index - leftmost_index + 1.

1from collections import deque
2
3class Node:
4    def __init__(self, val, left=None, right=None):
5        self.val = val
6        self.left = left
7        self.right = right
8
9def width_of_binary_tree(root):
10    if not root:
11        return 0
12
13    queue = deque([(root, 0)])
14    best = 0
15
16    while queue:
17        level_length = len(queue)
18        _, first_index = queue[0]
19        last_index = first_index
20
21        for _ in range(level_length):
22            node, index = queue.popleft()
23            normalized = index - first_index
24            last_index = normalized
25
26            if node.left:
27                queue.append((node.left, 2 * normalized))
28            if node.right:
29                queue.append((node.right, 2 * normalized + 1))
30
31        best = max(best, last_index + 1)
32
33    return best

Normalizing indexes at each level keeps the numbers small while preserving the width calculation.

Why Normalization Helps

In a very deep tree, raw index values can grow quickly because they double at each step. Python integers can handle that growth, but normalization still makes the code cleaner and easier to reason about.

By subtracting the leftmost index at the start of each level, you make the first node at that level position 0. Every other node keeps the correct relative distance from it, which is all the width formula actually needs.

Example Tree

Consider this tree:

1        1
2      /   \
3     2     3
4    /       \
5   4         7

At the bottom level, the actual node count is 2, but the indexed width is 4 because the nodes occupy positions with gaps between them. That is exactly why a plain node count is insufficient for some problem statements.

Complexity

The indexed BFS solution runs in O(n) time because each node is visited once. Space usage is O(w), where w is the maximum number of nodes held in the queue at any level.

That makes breadth-first search the standard solution for this problem. A depth-first version is possible, but BFS maps more naturally to level widths.

Common Pitfalls

• Counting nodes per level when the problem definition includes null-position gaps.
• Forgetting the + 1 in rightmost - leftmost + 1.
• Letting position indexes grow unnecessarily large instead of normalizing each level.
• Mixing one-based and zero-based index formulas.
• Not handling the empty tree case.

Summary

• Clarify whether width means node count or indexed width with gaps.
• For simple width, count nodes at each level with BFS.
• For indexed width, track complete-tree positions during level-order traversal.
• Compute each level's width as last_index - first_index + 1.
• Normalizing indexes per level keeps the implementation stable on deep trees.