# Maximum Width of Binary Tree – Leetcode Solution

In this post, we are going to solve the 662. Maximum Width of Binary Tree problem of Leetcode. This problem 662. Maximum Width of Binary Tree is a Leetcode medium level problem. Let’s see the code, 662. Maximum Width of Binary Tree – Leetcode Solution.

Contents

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

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

Now, let’s see the code of 662. Maximum Width of Binary Tree – Leetcode Solution.

# Maximum Width of Binary Tree – Leetcode Solution

### 662. Maximum Width of Binary Tree – Solution in 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 class Pair{
TreeNode node;
int idx;

Pair(TreeNode node,int idx){
this.node = node;
this.idx = idx;
}
}

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

int max = 0;

while(!q.isEmpty()){
int size = q.size();
int minL = q.peek().idx;
int maxL = q.peek().idx;
while(size-- > 0){
Pair rn = q.poll();
maxL = rn.idx;

if(rn.node.left != null ){
}

if(rn.node.right != null ){
}

}
max = Math.max(max,maxL - minL + 1);
}
return max;
}
}```

### 662. Maximum Width of Binary Tree – Solution in C++

```/**
* 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) {
if(root == NULL)
return 0;

int res = 1;
queue<pair<TreeNode*, int>> q;

q.push({root, 0});

while(!q.empty())
{
int cnt = q.size();

int start = q.front().second;
int end = q.back().second;

res = max(res,end-start + 1);

for(int i = 0; i <cnt; ++i)
{
pair<TreeNode*, int> p = q.front();

int idx = p.second - start;

q.pop();

if(p.first->left != NULL)
q.push({p.first->left, (long long)2 * idx + 1});

if(p.first->right != NULL)
q.push({p.first->right, (long long) 2 * idx + 2});
}
}

return res;

}
};```

### 662. Maximum Width of Binary Tree– Solution in Python

```# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def widthOfBinaryTree(self, root):
level_old, num_old, max_width = 1, 1, 0
queue = deque([[level_old,num_old,root]])

while queue:
[num, level, node] = queue.popleft()
if level > level_old:
level_old, num_old = level, num

max_width = max(max_width, num - num_old + 1)
if node.left:  queue.append([num*2,  level+1, node.left])
if node.right: queue.append([num*2+1,level+1, node.right])

return max_width
```

Note: This problem 662. Maximum Width of Binary Tree is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.