# Max width of binary tree

{% embed url="<https://leetcode.com/problems/maximum-width-of-binary-tree/description/>" %}

Solution 1. BFS with Node Indices: One solution is to perform a breadth-first search (BFS) of the tree, while keeping track of the indices of each node in the BFS order. At each level, we can calculate the width as the difference between the indices of the first and last non-null nodes. We can keep track of the maximum width seen so far and return it at the end. \
This solution has a time complexity of O(n) and a space complexity of O(n).<br>

```java
class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 1));
        int maxWidth = 1;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int minIndex = queue.peek().getValue();
            
            for (int i = 0; i < levelSize; i++) {
                Pair<TreeNode, Integer> nodePair = queue.poll();
                TreeNode node = nodePair.getKey();
                int index = nodePair.getValue();
                
                if (node.left != null) {
                    queue.offer(new Pair<>(node.left, 2 * index));
                }
                if (node.right != null) {
                    queue.offer(new Pair<>(node.right, 2 * index + 1));
                }
                maxWidth = Math.max(maxWidth, index - minIndex + 1);
            }
            
            
        }
        
        return maxWidth;
    }
}
```

Solution 2. DFS with Hash Map: A third solution is to perform a depth-first search (DFS) of the tree, while keeping track of the minimum and maximum x-coordinates of nodes at each level using a hash map. Specifically, we can traverse the tree recursively, passing down the current level and the x-coordinate of the current node. At each node, we can update the minimum and maximum x-coordinates for the current level in the hash map. We can then recursively traverse the left and right subtrees, passing down the current level + 1 and the updated x-coordinates. After the traversal, we can iterate over the hash map and calculate the width at each level as the difference between the maximum and minimum x-coordinates. We can keep track of the maximum width seen so far and return it at the end. \
This solution has a time complexity of O(n) and a space complexity of O(h), where h is the height of the tree (i.e., the maximum depth of the tree).

```java
class Solution {
   // Similar to level traverse with DFS
    public int widthOfBinaryTree(TreeNode root) {
        // Initialize a hash map to keep track of min and max x-coordinates at each level
        Map<Integer, Pair<Integer, Integer>> levelMap = new HashMap<>();
        
        // Call the recursive traversal function
        traverse(root, 0, 0, levelMap);
        
        // Iterate over the level map to calculate the maximum width
        int maxWidth = 0;
        for (int level : levelMap.keySet()) {
            Pair<Integer, Integer> minMaxPair = levelMap.get(level);
            int width = minMaxPair.getValue() - minMaxPair.getKey() + 1;
            maxWidth = Math.max(maxWidth, width);
        }
        
        return maxWidth;
    }
    
    // Define a helper function to traverse the tree recursively
    private void traverse(TreeNode node, int level, int x, Map<Integer, Pair<Integer, Integer>> levelMap) {
        if (node == null) {
            return;
        }
        
        // Update the min and max x-coordinates for the current level
        if (!levelMap.containsKey(level)) {
            levelMap.put(level, new Pair(x, x));
        } else {
            Pair<Integer, Integer> prevPair = levelMap.get(level);
            levelMap.put(level, new Pair(prevPair.getKey(), x));
        }
        
        // Recursively traverse the left and right subtrees
        traverse(node.left, level + 1, 2 * x, levelMap);
        traverse(node.right, level + 1, 2 * x + 1, levelMap);
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://coding.bea.ai/tree/typical-problems-and-solutions/max-width-of-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.