## Algorithm

Problem Name: 662. Maximum Width of Binary Tree

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`

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
// BFS
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if(!root) return 0;
int maxWidth = 1;
deque<pair < TreeNode*, int>>cur;
deque < pair;
if(p.first->left) next.push_back({p.first->left, p.second * 2});
if(p.first->right) next.push_back({p.first->right, p.second * 2 + 1});
if(cur.empty() && !next.empty()){
swap(cur, next);
maxWidth = max(maxWidth, cur.back().second - cur.front().second + 1);
}
}
return maxWidth;
}
};

// DFS
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int maxWidth = 0;
vector<int>v;
DFS(root, v, 1, 0, maxWidth);
return maxWidth;
}

void DFS(TreeNode* root, vector<int>& v, int tag, int level, int& maxWidth){
if(!root) return;
if(v.size() == level) v.push_back(tag);
maxWidth = max(maxWidth, tag - v[level] + 1);
DFS(root->left, v, tag * 2, level + 1, maxWidth);
DFS(root->right, v, tag * 2 + 1, level + 1, maxWidth);
}
};
``````
Copy The Code &

Input

cmd
root = [1,3,2,5,3,null,9]

Output

cmd
4

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int widthOfBinaryTree(TreeNode root) {
int maxWidth = 0;
Queue < TreeNode> queue = new LinkedList<>();
Map map = new HashMap<>();
map.put(root, 1);
while (!queue.isEmpty()) {
int size = queue.size();
int start = 0;
int end = 0;
for (int i = 0; i  <  size; i++) {
TreeNode node = queue.poll();
if (i == 0) {
start = map.get(node);
}
if (i == size - 1) {
end = map.get(node);
}
if (node.left != null) {
map.put(node.left, map.get(node) * 2);
}
if (node.right != null) {
map.put(node.right, map.get(node) * 2 + 1);
}
}
maxWidth = Math.max(maxWidth, end - start + 1);
}
return maxWidth;
}
}
``````
Copy The Code &

Input

cmd
root = [1,3,2,5,3,null,9]

Output

cmd
4

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const widthOfBinaryTree = function(root) {
const mins = [0]
let max = 0

dfs(root, 0, 0)
return max

// depth first search
function dfs(currentNode, depth, position) {
if (!currentNode) return
if (depth === mins.length) {
mins[depth] = position
}

const delta = position - mins[depth]
max = Math.max(max, delta + 1)
dfs(currentNode.left, depth + 1, delta * 2)
dfs(currentNode.right, depth + 1, delta * 2 + 1)
}
}
``````
Copy The Code &

Input

cmd
root = [1,3,2,5,null,null,9,6,null,7]

Output

cmd
7

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def widthOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
dic, stack, res = {root: 1}, [root], 0
while any(stack):
tmp, mn ,mx = [], float("inf"), - float("inf")
for node in stack:
res = max(res, dic[stack[-1]] - dic[stack[0]] + 1)
if node.left: tmp, dic[node.left] = tmp + [node.left], dic[node] * 2 - 1
if node.right: tmp, dic[node.right] = tmp + [node.right], dic[node] * 2
stack = tmp
return res
``````
Copy The Code &

Input

cmd
root = [1,3,2,5,null,null,9,6,null,7]

Output

cmd
7

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0662_MaximumWidthOfBinaryTree
{
public int WidthOfBinaryTree(TreeNode root)
{
return dfs(root, 0, 1, new Dictionary < int, int>(), new Dictionary<int, int>());
}

public int dfs(TreeNode root, int level, int order, IDictionary<int, int> start, IDictionary<int, int> end)
{
if (root == null) return 0;
if (start.Count == level)
{
start[level] = order;
end[level] = order;
}
else
end[level] = order;

int cur = end[level] - start[level] + 1;
int left = dfs(root.left, level + 1, 2 * order, start, end);
int right = dfs(root.right, level + 1, 2 * order + 1, start, end);
return Math.Max(cur, Math.Max(left, right));
}
}
}
``````
Copy The Code &

Input

cmd
root = [1,3,2,5]

Output

cmd
2