Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Maximum Width of Binary Tree
• Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Problem gist

The input is the root of a binary tree. The task is to find the largest width across all levels.

The subtle part is how width is defined. It is not just the number of real nodes on a level. The width runs from the leftmost real node to the rightmost real node on that level, counting the missing null positions between them as if the tree were laid out like a complete binary tree.

For example, a level may contain two real nodes far apart because their missing siblings and cousins sit between them conceptually. Those gaps still count toward the width.

Deriving the approach

Start with ordinary breadth-first search. BFS is a natural fit because width is a level-by-level property: process every node currently in the queue, then move to the next level.

The missing piece is how to account for null gaps without actually storing null nodes. The clean trick is to assign each real node the index it would have in a complete binary tree:

• The root has index 0.
• A node at index i has left child 2 * i and right child 2 * i + 1.

With those indices, the width of a level is:

rightmost_index - leftmost_index + 1

That formula automatically counts the empty positions between the endpoints. There is no need to enqueue null children.

One practical detail matters in languages with fixed-size integers, and it is still a good habit in Python: normalize indices at each level. Before expanding a level, subtract that level’s leftmost index from every node index. This preserves all distances inside the level, but keeps the child indices small for deep or sparse trees.

The optimal BFS visits each real node once. Time complexity is O(n), where n is the number of nodes. Auxiliary space is O(w), where w is the maximum number of real nodes stored in the queue for a level.

Python solution

from collections import deque
from typing import Deque, Optional, Tuple


class TreeNode:
    """Binary tree node. LeetCode provides an equivalent class."""

    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ) -> 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

        widest_level = 0
        current_level: Deque[Tuple[TreeNode, int]] = deque([(root, 0)])

        while current_level:
            leftmost_index = current_level[0][1]
            rightmost_index = current_level[-1][1]
            widest_level = max(widest_level, rightmost_index - leftmost_index + 1)

            level_size = len(current_level)

            for _ in range(level_size):
                node, index = current_level.popleft()
                normalized_index = index - leftmost_index
                self._append_children(current_level, node, normalized_index)

        return widest_level

    @staticmethod
    def _append_children(
        queue: Deque[Tuple[TreeNode, int]],
        node: TreeNode,
        normalized_index: int,
    ) -> None:
        # Normalization preserves relative spacing while preventing huge indices.
        if node.left is not None:
            queue.append((node.left, 2 * normalized_index))
        if node.right is not None:
            queue.append((node.right, 2 * normalized_index + 1))

Why this works

The index of a node represents where that node would appear in a complete-tree layout. Because complete-tree indexing gives every possible position a unique number, the distance between the leftmost and rightmost real nodes on a level is exactly the number of slots between them, including missing slots.

BFS guarantees that all nodes in the queue at the start of an iteration belong to the same depth. That makes queue[0] the leftmost real node at that level and queue[-1] the rightmost real node, assuming children are appended left child before right child. The width formula is therefore computed at the only moment when the queue represents a full level.

Normalizing by the level’s leftmost index does not change any width. Subtracting the same number from every index shifts the level to start near zero, but all differences remain identical. Child indices generated from normalized parent indices are also shifted by a constant relative to the unnormalized layout, so future width differences remain valid.

Common pitfalls

Do not count only the real nodes on a level. That misses cases where two nodes are separated by many absent positions.

Do not enqueue null nodes to model the gaps. It can blow up exponentially on sparse deep trees, and it is unnecessary once positions are tracked with indices.

Do not let child order vary. The queue should always receive the left child before the right child so the first and last queued nodes match the visual left-to-right order of the next level.

Interview follow-ups

Can this be solved with DFS?

Yes. A depth-first traversal can store the first index seen at each depth. When visiting another node at that same depth, compute current_index - first_index_at_depth + 1 and update the answer.

This works because the first node encountered at a depth during a left-first DFS is the leftmost real node for that level. The traversal still uses complete-tree indices to account for missing positions. The time complexity remains O(n). The tradeoff is stack space: recursive DFS uses O(h) call stack space, where h is the tree height, and a very deep tree may exceed Python’s recursion limit unless implemented iteratively.

Why normalize indices instead of using the raw complete-tree index?

Raw complete-tree indices grow exponentially with depth. Python can handle large integers, but large integer arithmetic is slower and harder to reason about. In languages like Java, C++, or Go, raw indices can overflow fixed-size integer types.

Normalizing each level subtracts the leftmost index before creating child positions. Width depends only on differences between positions, so this subtraction keeps the math equivalent while keeping numbers small. It is a low-cost defensive habit that makes the approach portable.

What if the interviewer asks for the nodes on the widest level too?

Keep the same BFS structure, but when a level produces a new maximum width, record that level’s real node values or node references. The width calculation still uses indices, because null gaps may matter even though the output contains only real nodes.

This adds O(k) extra space for the saved widest level, where k is the number of real nodes on that level. The traversal time remains O(n).

How would the solution change for a one-indexed layout?

It barely changes. The root can be index 1, the left child can be 2 * i, and the right child can be 2 * i + 1. The width formula is still rightmost_index - leftmost_index + 1.

Zero-indexing is convenient because the root starts at 0, but the proof is the same. Any consistent complete-tree indexing scheme works as long as parent-child positions preserve the same relative gaps.

Why is BFS often preferred over DFS for this problem?

BFS mirrors the problem statement directly: width is a level property, and the queue exposes one full level at a time. That makes the code compact and makes the width formula visible.

DFS is equally valid, but it needs an extra structure mapping depth to the first index at that depth. BFS usually has fewer moving parts in an interview, while DFS is a useful follow-up to show that the key idea is not BFS itself but complete-tree position indexing.