LeetCode 662 - Maximum Width of Binary Tree

LeetCode Problem 662

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to compute the maximum width among all levels of a binary tree. The important detail is that the width is not simply the number of non-null nodes at a level. Instead, the width must include the positions of missing nodes that would exist if the tree were represented as a complete binary tree.

In a complete binary tree, every node has a conceptual position index. If a node has index i, then:

• Its left child would have index 2 * i
• Its right child would have index 2 * i + 1

Even if some children are missing, their positions still matter for calculating width.

For example, consider this level:

5, 3, null, 9

Although there are only three actual nodes, the distance between the leftmost node (5) and the rightmost node (9) spans four positions in the complete binary tree representation. Therefore, the width is 4.

The input is the root node of a binary tree. The output is a single integer representing the maximum width across all levels.

The constraints are relatively small, with at most 3000 nodes. This means an O(n) or O(n log n) solution is more than sufficient. However, there is an important implementation detail involving position indices. If we continuously double indices at every level, the values can grow very large for deep trees. Even though the final answer fits within a 32-bit signed integer, intermediate indices may become large if we are not careful.

Several edge cases are important:

• A tree with only one node should return width 1
• A skewed tree still has width 1 at every level
• Sparse trees with large gaps between nodes can produce large widths
• Deep trees can cause index overflow if indices are not normalized

Approaches

Brute Force Approach

A naive idea is to explicitly build the complete binary tree representation level by level, including null placeholders. At each level, we could store every node position, including missing nodes, and then measure the distance between the first and last non-null node.

This approach works because it directly models the problem definition. However, it becomes very inefficient because the number of placeholder null nodes grows exponentially with tree depth. A sparse tree of depth h could require storing up to 2^h positions.

Even though the actual number of nodes is only at most 3000, the conceptual complete tree can become much larger. Therefore, explicitly representing missing nodes is wasteful and unnecessary.

Optimal Approach

The key insight is that we do not need to store missing nodes explicitly. We only need their conceptual positions.

We can perform a Breadth-First Search level by level while assigning each node a complete-binary-tree index:

• Root gets index 0
• Left child gets 2 * index
• Right child gets 2 * index + 1

At every level:

• The first node's index gives the left boundary
• The last node's index gives the right boundary
• Width becomes:

last_index - first_index + 1

To prevent indices from growing excessively large, we normalize indices at each level by subtracting the first index in that level. This keeps numbers small while preserving relative distances.

This gives a clean O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^h)	O(2^h)	Explicitly stores null positions in a complete tree representation
Optimal	O(n)	O(n)	BFS with conceptual indices and level normalization

Algorithm Walkthrough

1. Start a Breadth-First Search using a queue.
2. Store both the node and its conceptual index in the queue. Begin with:

• root at index 0

3. Process the tree one level at a time.

• The queue size at the start of each iteration tells us how many nodes belong to the current level.

4. Record the first index in the level.

• This becomes the normalization base.
• Subtracting it from every index in the level prevents large integer growth.

5. For every node in the current level:

• Remove it from the queue

• Normalize its index

• Add its children with calculated indices:

• Left child: 2 * normalized_index

• Right child: 2 * normalized_index + 1

6. Track the normalized index of:

• The first node in the level
• The last node in the level

7. Compute the width:

width = last_index - first_index + 1

8. Update the global maximum width.
9. Continue until the queue becomes empty.

Why it works

The algorithm works because the assigned indices exactly match the positions nodes would occupy in a complete binary tree. The difference between the leftmost and rightmost indices therefore captures all gaps between them, including missing nodes.

Normalizing indices does not affect the width because subtracting the same value from all positions preserves relative distances.

Python Solution

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 not root:
            return 0

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

        while queue:
            level_size = len(queue)
            level_start_index = queue[0][1]

            first_index = 0
            last_index = 0

            for i in range(level_size):
                node, index = queue.popleft()

                normalized_index = index - level_start_index

                if i == 0:
                    first_index = normalized_index

                if i == level_size - 1:
                    last_index = normalized_index

                if node.left:
                    queue.append((node.left, 2 * normalized_index))

                if node.right:
                    queue.append((node.right, 2 * normalized_index + 1))

            current_width = last_index - first_index + 1
            max_width = max(max_width, current_width)

        return max_width

The implementation begins with a standard BFS queue. Each queue entry stores both the node and its conceptual index.

At the start of every level, the leftmost index is recorded as level_start_index. Every node index in that level is normalized by subtracting this value. This prevents unnecessary integer growth while preserving positional relationships.

The algorithm tracks the first and last normalized indices in the level. Their difference plus one gives the width.

Children are inserted using the complete-binary-tree indexing rules. Because BFS processes nodes level by level, every level width is computed independently and correctly.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Pair struct {
	node  *TreeNode
	index int
}

func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}

	queue := []Pair{{root, 0}}
	maxWidth := 0

	for len(queue) > 0 {
		levelSize := len(queue)
		levelStartIndex := queue[0].index

		firstIndex := 0
		lastIndex := 0

		for i := 0; i < levelSize; i++ {
			pair := queue[0]
			queue = queue[1:]

			node := pair.node
			normalizedIndex := pair.index - levelStartIndex

			if i == 0 {
				firstIndex = normalizedIndex
			}

			if i == levelSize-1 {
				lastIndex = normalizedIndex
			}

			if node.Left != nil {
				queue = append(queue, Pair{
					node:  node.Left,
					index: 2 * normalizedIndex,
				})
			}

			if node.Right != nil {
				queue = append(queue, Pair{
					node:  node.Right,
					index: 2*normalizedIndex + 1,
				})
			}
		}

		currentWidth := lastIndex - firstIndex + 1

		if currentWidth > maxWidth {
			maxWidth = currentWidth
		}
	}

	return maxWidth
}

The Go implementation follows the same BFS strategy as the Python version. Since Go does not have tuples, a custom Pair struct stores the node and index together.

Go uses nil for missing child pointers instead of Python's None. The queue is implemented using slices, removing elements from the front with slicing operations.

Index normalization is especially useful in Go because integer overflow can otherwise become an issue in very deep trees.

Worked Examples

Example 1

Input: [1,3,2,5,3,null,9]

Tree structure:

        1
      /   \
     3     2
    / \     \
   5   3     9

Level-by-Level Processing

Level	Queue Contents (node, index)	Width
0	[(1,0)]	1
1	[(3,0), (2,1)]	2
2	[(5,0), (3,1), (9,3)]	4

Maximum width becomes 4.

Example 2

Input: [1,3,2,5,null,null,9,6,null,7]

Tree structure:

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

Level-by-Level Processing

Level	Queue Contents (node, index)	Width
0	[(1,0)]	1
1	[(3,0), (2,1)]	2
2	[(5,0), (9,3)]	4
3	[(6,0), (7,6)]	7

Maximum width becomes 7.

Example 3

Input: [1,3,2,5]

Tree structure:

      1
    /   \
   3     2
  /
 5

Level-by-Level Processing

Level	Queue Contents (node, index)	Width
0	[(1,0)]	1
1	[(3,0), (2,1)]	2
2	[(5,0)]	1

Maximum width becomes 2.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is visited exactly once
Space	O(n)	The queue may store an entire tree level

The BFS traversal processes each node one time, making the total runtime linear in the number of nodes. The queue can contain up to all nodes in the widest level of the tree, which in the worst case is proportional to n.

Test Cases

from collections import deque
from typing import Optional

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 not root:
            return 0

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

        while queue:
            level_size = len(queue)
            start_index = queue[0][1]

            first = 0
            last = 0

            for i in range(level_size):
                node, index = queue.popleft()

                normalized = index - start_index

                if i == 0:
                    first = normalized

                if i == level_size - 1:
                    last = normalized

                if node.left:
                    queue.append((node.left, 2 * normalized))

                if node.right:
                    queue.append((node.right, 2 * normalized + 1))

            max_width = max(max_width, last - first + 1)

        return max_width

solver = Solution()

# Example 1
root1 = TreeNode(1)
root1.left = TreeNode(3)
root1.right = TreeNode(2)
root1.left.left = TreeNode(5)
root1.left.right = TreeNode(3)
root1.right.right = TreeNode(9)

assert solver.widthOfBinaryTree(root1) == 4  # standard sparse width case

# Example 2
root2 = TreeNode(1)
root2.left = TreeNode(3)
root2.right = TreeNode(2)
root2.left.left = TreeNode(5)
root2.right.right = TreeNode(9)
root2.left.left.left = TreeNode(6)
root2.right.right.right = TreeNode(7)

assert solver.widthOfBinaryTree(root2) == 7  # large conceptual gap

# Example 3
root3 = TreeNode(1)
root3.left = TreeNode(3)
root3.right = TreeNode(2)
root3.left.left = TreeNode(5)

assert solver.widthOfBinaryTree(root3) == 2  # uneven tree

# Single node
root4 = TreeNode(1)

assert solver.widthOfBinaryTree(root4) == 1  # minimal tree

# Left-skewed tree
root5 = TreeNode(1)
root5.left = TreeNode(2)
root5.left.left = TreeNode(3)
root5.left.left.left = TreeNode(4)

assert solver.widthOfBinaryTree(root5) == 1  # no branching

# Right-skewed tree
root6 = TreeNode(1)
root6.right = TreeNode(2)
root6.right.right = TreeNode(3)

assert solver.widthOfBinaryTree(root6) == 1  # all nodes on one side

# Perfect binary tree
root7 = TreeNode(1)
root7.left = TreeNode(2)
root7.right = TreeNode(3)
root7.left.left = TreeNode(4)
root7.left.right = TreeNode(5)
root7.right.left = TreeNode(6)
root7.right.right = TreeNode(7)

assert solver.widthOfBinaryTree(root7) == 4  # fully populated level

# Sparse deep tree
root8 = TreeNode(1)
root8.left = TreeNode(2)
root8.right = TreeNode(3)
root8.left.left = TreeNode(4)
root8.right.right = TreeNode(5)

assert solver.widthOfBinaryTree(root8) == 4  # width includes null gaps

Test	Why
Standard sparse tree	Validates width counting with internal null gaps
Large conceptual gap	Confirms correct positional indexing
Uneven tree	Ensures asymmetric trees work correctly
Single node	Smallest valid input
Left-skewed tree	Width should remain 1
Right-skewed tree	Confirms handling of missing left children
Perfect binary tree	Verifies standard complete-tree behavior
Sparse deep tree	Tests conceptual width calculation

Edge Cases

Single Node Tree

A tree containing only the root node is the smallest possible valid input. A buggy implementation might incorrectly return 0 if width initialization is mishandled. This implementation correctly processes the root level and returns width 1.

Highly Skewed Trees

A tree where every node only has a left child or only a right child has width 1 at every level. Some implementations mistakenly interpret increasing positional indices as increasing width. Since the algorithm computes width from the first and last node in the same level, skewed trees correctly produce width 1.

Sparse Trees With Large Gaps

The most important edge case is a sparse tree where nodes are far apart conceptually. For example:

        1
      /   \
     2     3
    /       \
   4         5

The bottom level has only two nodes, but their conceptual positions span four slots. A naive node-counting solution would incorrectly return 2. The positional indexing approach correctly counts the null gaps and returns 4.

Deep Trees And Integer Growth

Because child indices double at every level, deep trees can produce very large numbers. Although Python integers can grow arbitrarily large, other languages may overflow. The implementation avoids this issue by normalizing indices at each level, keeping numbers small while preserving distances between nodes.