Maximum Width of Binary Tree - Video Solutions

Problem Overview: You are given the root of a binary tree. The width of a level is defined as the distance between the leftmost and rightmost non-null nodes, counting the null positions that would exist in a complete binary tree. The task is to compute the maximum width across all levels.

Approach 1: Level Order Traversal with Position Tracking (O(n) time, O(n) space)

This approach performs a standard Breadth-First Search using a queue. Each node is assigned a positional index as if the tree were stored in an array representation of a complete binary tree. The root starts at index 0, the left child gets 2*i, and the right child gets 2*i + 1. For every level, record the index of the first and last node in the queue. The width of that level is last_index - first_index + 1. The algorithm iterates level by level, updating the maximum width seen so far.

This works because positional indices preserve the virtual gaps between nodes that would appear in a complete tree layout. Even if some nodes are missing, the index difference still captures the correct width. Since each node is processed exactly once, the traversal runs in O(n) time with O(n) queue space in the worst case.

Approach 2: DFS with Position Tracking (O(n) time, O(h) space)

A Depth-First Search can compute the same width by tracking the first index encountered at every depth. Traverse the binary tree recursively while passing two values: the current depth and the node's positional index. When visiting a depth for the first time, store that index as the leftmost position for that level. For every node visited later at the same depth, compute the width using current_index - first_index_at_depth + 1.

This approach avoids storing entire levels like BFS. Instead, it only stores the first index for each depth and relies on recursion to explore the tree. The maximum width is updated during traversal. Because each node is visited once, the time complexity remains O(n). Space complexity becomes O(h) for recursion depth, where h is the tree height (up to O(n) in skewed trees).

Recommended for interviews: The level-order BFS approach is the most common interview solution. It clearly demonstrates understanding of tree traversal and how to simulate complete-tree indexing. The DFS variant shows deeper insight and uses less auxiliary memory when the tree height is small. Showing BFS first and then mentioning DFS as an optimization signals strong problem-solving depth.