# Maximum Width of Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-width-of-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/maximum-width-of-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-width-of-binary-tree/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/maximum-width-of-binary-tree/image1.jpg) 

**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:**

![](https://assets.glich.co/dsa/maximum-width-of-binary-tree/image2.jpg) 

**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`

# Approaches
## Breadth-First Search (Level-Order Traversal)
This approach uses a Breadth-First Search (BFS) to traverse the tree level by level. The core idea is to assign a numerical index to each node as if it were in a complete binary tree. The width of a level is then the difference between the indices of the rightmost and leftmost nodes, plus one.
**Time:** O(N), where N is the number of nodes in the tree. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum number of nodes at any single level. In the worst-case scenario of a complete binary tree, the last level can contain up to `(N+1)/2` nodes, making the space complexity O(N).
**Pros:** Intuitive and straightforward for a level-based problem.; Guarantees finding the maximum width because it systematically checks every level.; Generally more space-efficient than DFS for very deep and narrow trees.
**Cons:** Can be less space-efficient than DFS for tall, skinny trees, as the queue can grow to the width of the widest level.; The logic for re-basing indices at each level adds a bit of complexity compared to a standard BFS.
### Explanation
We use a queue to perform the level-order traversal. Instead of just storing the tree nodes, we store pairs of `(TreeNode, index)`. The root node is assigned index 0. For any node at index `i`, its left child would be at `2*i + 1` and its right child at `2*i + 2` in a complete binary tree.

A potential issue is that these indices can grow very large and cause an integer overflow, especially in deep trees. To prevent this, we re-normalize the indices at the beginning of each level. The index of the first node at each level is used as an offset. For any node with an original index `p_idx` at a level where the leftmost node has index `min_idx`, its new relative index becomes `p_idx - min_idx`. The children's indices are then calculated based on this new relative index, which keeps the index values small and manageable.

```java
// Helper class to store node and its index
class NodeInfo {
    TreeNode node;
    int index;
    NodeInfo(TreeNode node, int index) {
        this.node = node;
        this.index = index;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<NodeInfo> queue = new LinkedList<>();
        queue.offer(new NodeInfo(root, 0));
        int maxWidth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            NodeInfo head = queue.peek();
            int startIdx = head.index;
            int leftmostIdx = 0, rightmostIdx = 0;

            for (int i = 0; i < levelSize; i++) {
                NodeInfo current = queue.poll();
                TreeNode node = current.node;
                int index = current.index;

                if (i == 0) {
                    leftmostIdx = index;
                }
                if (i == levelSize - 1) {
                    rightmostIdx = index;
                }

                // Re-base index to prevent overflow
                int relativeIndex = index - startIdx;

                if (node.left != null) {
                    // Use long for intermediate calculation to prevent overflow
                    queue.offer(new NodeInfo(node.left, (int)(2L * relativeIndex + 1)));
                }
                if (node.right != null) {
                    queue.offer(new NodeInfo(node.right, (int)(2L * relativeIndex + 2)));
                }
            }
            maxWidth = Math.max(maxWidth, rightmostIdx - leftmostIdx + 1);
        }
        return maxWidth;
    }
}
```
### Algorithm
*   Create a queue to store pairs of `(TreeNode, Integer)` representing the node and its calculated index.
*   If the root is null, return 0.
*   Add the root node with an initial index of 0 to the queue.
*   Initialize a variable `maxWidth` to 0.
*   Loop while the queue is not empty, processing one level at a time:
    *   Get the number of nodes on the current level (`levelSize`).
    *   Peek at the first node in the queue to get the starting index for this level (`startIdx`). This is used for re-basing indices to prevent overflow.
    *   Initialize `leftmostIdx` and `rightmostIdx` for the current level.
    *   Loop `levelSize` times to process all nodes on the level:
        *   Dequeue a `(node, index)` pair.
        *   If it's the first node of the level, store its index in `leftmostIdx`.
        *   If it's the last node of the level, store its index in `rightmostIdx`.
        *   Calculate a `relativeIndex = index - startIdx`.
        *   If the node has a left child, enqueue it with a new index of `2 * relativeIndex + 1`.
        *   If the node has a right child, enqueue it with a new index of `2 * relativeIndex + 2`.
    *   After the level is processed, calculate its width as `rightmostIdx - leftmostIdx + 1`.
    *   Update `maxWidth` with the maximum width found so far.
*   Return `maxWidth`.

## Depth-First Search (Pre-order Traversal)
This approach uses a Depth-First Search (DFS) to traverse the tree. Instead of processing level by level, we traverse deep into the tree, keeping track of the first (leftmost) node encountered at each depth. The width is then updated whenever we visit a node.
**Time:** O(N), where N is the number of nodes in the tree. Each node is visited exactly once. · **Space:** O(H), where H is the height of the tree. This space is used for the recursion stack and the `leftmostIndices` list. In the worst case of a skewed tree, H can be N, making the space complexity O(N).
**Pros:** Can be more space-efficient than BFS for wide, shallow trees, as its space complexity depends on the tree's height (O(H)).; The recursive implementation is often considered elegant and can be more concise.
**Cons:** Can be less space-efficient than BFS for wide, shallow trees due to the recursion stack depth.; In the worst case of a skewed tree, the recursion depth can be O(N), potentially leading to a StackOverflowError for very large N.; The logic for handling indices to prevent overflow requires careful use of a larger data type like `long`.
### Explanation
The key idea is to maintain a list that stores the index of the leftmost node for each depth. Let's call this `leftmostIndices`. `leftmostIndices.get(d)` will hold the index of the first node visited at depth `d`.

We perform a pre-order traversal (`node`, then `left`, then `right`). This ensures that for any given depth, the first time we visit it, we are at its leftmost node.

To avoid integer overflow with large indices, we use a clever relative indexing scheme. We define the root's index as 0. For a parent node with relative index `i`, its left child's relative index is `2*i`, and its right child's is `2*i + 1`. This scheme works because the width calculation `rightmost_idx - leftmost_idx + 1` is preserved. The maximum value of the relative index is related to the maximum width, which is guaranteed to fit in a 32-bit integer. However, the intermediate calculations (`2*i`) can exceed the `int` range, so we use `long` for the index parameter to be safe.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    private int maxWidth = 0;
    private List<Long> leftmostIndices;

    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        leftmostIndices = new ArrayList<>();
        dfs(root, 0, 0L);
        return maxWidth;
    }

    private void dfs(TreeNode node, int depth, long index) {
        if (node == null) {
            return;
        }

        // First time visiting this depth, record the leftmost index
        if (depth == leftmostIndices.size()) {
            leftmostIndices.add(index);
        }

        // Calculate width for the current level. The difference will fit in an int.
        long currentWidth = index - leftmostIndices.get(depth) + 1;
        maxWidth = Math.max(maxWidth, (int)currentWidth);

        // Recurse for children with new relative indices
        dfs(node.left, depth + 1, 2 * index);
        dfs(node.right, depth + 1, 2 * index + 1);
    }
}
```
### Algorithm
*   Initialize a member variable `maxWidth` to 0 and a list `leftmostIndices` to store the first index encountered at each depth.
*   Define a recursive function `dfs(node, depth, index)`.
*   Start the process by calling `dfs(root, 0, 0L)`.
*   Inside the `dfs` function:
    *   Base case: if `node` is null, return.
    *   If `depth` equals the size of `leftmostIndices`, it's the first time we are visiting this level. Since we traverse left-first, this must be the leftmost node. Add its `index` to `leftmostIndices`.
    *   Calculate the width for the current node's level: `width = index - leftmostIndices.get(depth) + 1`.
    *   Update `maxWidth = max(maxWidth, width)`.
    *   Recurse on the left child: `dfs(node.left, depth + 1, 2 * index)`.
    *   Recurse on the right child: `dfs(node.right, depth + 1, 2 * index + 1)`.
*   Return `maxWidth`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int widthOfBinaryTree ( TreeNode root ) { Deque < Pair < TreeNode , Integer >> q = new ArrayDeque <>(); q . offer ( new Pair <>( root , 1 )); int ans = 0 ; while (! q . isEmpty ()) { ans = Math . max ( ans , q . peekLast (). getValue () - q . peekFirst (). getValue () + 1 ); for ( int n = q . size (); n > 0 ; -- n ) { var p = q . pollFirst (); root = p . getKey (); int i = p . getValue (); if ( root . left != null ) { q . offer ( new Pair <>( root . left , i << 1 )); } if ( root . right != null ) { q . offer ( new Pair <>( root . right , i << 1 | 1 )); } } } return ans ; } }
```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int widthOfBinaryTree ( TreeNode * root ) { queue < pair < TreeNode * , int >> q ; q . push ({ root , 1 }); int ans = 0 ; while ( ! q . empty ()) { ans = max ( ans , q . back (). second - q . front (). second + 1 ); int i = q . front (). second ; for ( int n = q . size (); n ; -- n ) { auto p = q . front (); q . pop (); root = p . first ; int j = p . second ; if ( root -> left ) q . push ({ root -> left , ( j << 1 ) - ( i << 1 )}); if ( root -> right ) q . push ({ root -> right , ( j << 1 | 1 ) - ( i << 1 )}); } } return ans ; } };
```

### Python

```python
# 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 : ans = 0 q = deque ([( root , 1 )]) while q : ans = max ( ans , q [ - 1 ][ 1 ] - q [ 0 ][ 1 ] + 1 ) for _ in range ( len ( q )): root , i = q . popleft () if root . left : q . append (( root . left , i << 1 )) if root . right : q . append (( root . right , i << 1 | 1 )) return ans
```