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.

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;
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(root,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 ){
                    q.add(new Pair(rn.node.left,2*rn.idx + 1));
                }
                
                if(rn.node.right != null ){
                    q.add(new Pair(rn.node.right,2*rn.idx + 2));
                }
                
            }
            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.