Maximum Width of Binary Tree - Solution & Explanation
Problem Statement
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will in the range of a 32-bit signed integer.
Example 1:
Input: root = [1,3,2,5,3,null,9] Output: 4 Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).
Example 2:
Input: root = [1,3,2,5,null,null,9,6,null,7] Output: 7 Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
Example 3:
Input: root = [1,3,2,5] Output: 2 Explanation: The maximum width exists in the second level with length 2 (3,2).
Constraints:
- The number of nodes in the tree is in the range
[1, 3000]. -100 <= Node.val <= 100
Approach Overview
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.
Approach 1: Level Order Traversal with Position Tracking
To solve the problem, we can perform a level order traversal (breadth-first search) of the tree using a queue. Each node will be annotated with a position value, starting with the root being assigned the position 0. As we traverse each level, we calculate the width as the difference between the position of the last node and the first node of that level plus one. This approach ensures that we take into account null positions that would exist in a perfect binary tree.
This Python solution uses a queue to perform a level order traversal. Each node's position is calculated by multiplying its parent position by 2 and adding 1 for right children. The width of each level is calculated using the positions assigned to each node.
Complexity
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed exactly once.
Space Complexity: O(w), where w is the maximum width of the tree, held in the queue at any level.
Approach 2: DFS with Position Tracking
An alternative approach involves using depth-first search (DFS) to traverse the tree while maintaining a map of the first position of each level. By keeping track of each node’s depth and position, we can determine the width of any tree level by computing the difference between the first and the current node's position at that depth.
This Python solution implements DFS to visit each node, mapping each level's first node position. We calculate width by comparing the position of the current node to this first node's position at each level.
Complexity
Time Complexity: O(n), visiting each node recursively.
Space Complexity: O(d), where d is the max depth of the tree, accounting for the recursion stack.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Level Order Traversal with Position Tracking | Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed exactly once. Space Complexity: O(w), where w is the maximum width of the tree, held in the queue at any level. |
| DFS with Position Tracking | Time Complexity: O(n), visiting each node recursively. Space Complexity: O(d), where d is the max depth of the tree, accounting for the recursion stack. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal with Position Tracking (BFS) | O(n) | O(n) | Best general solution. Easy to reason about because width is computed level by level. |
| DFS with Position Tracking | O(n) | O(h) | Useful when avoiding large queues. Works well when tree height is relatively small. |
Video Solution
L28. Maximum Width of Binary Tree | C++ | Java • take U forward • 469,425 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Width of Binary Tree easy or hard?
Maximum Width of Binary Tree Python/Java solution
How to solve Maximum Width of Binary Tree in O(n)?
What is the best approach for Maximum Width of Binary Tree?
Is Maximum Width of Binary Tree asked at Google/Amazon/Meta?
What data structure is used in Maximum Width of Binary Tree?
What is the time complexity of Maximum Width of Binary Tree?
Ready to solve this problem?
Practice Maximum Width of Binary Tree with our built-in code editor and test cases.
Practice on FleetCode