Problem Statement:

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

Solution:

Clearly this question pertains to BFS. Here is the skeleton of BFS in binary tree.

 
void BFS(TreeNode* root)
{
    Q.push(root);
    while(!Q.empty())
    {
        for (int i=Q.size(); i>0; i--)
        {
            TreeNode* cur = Q.front();
            Q.pop();
            if(cur->left) Q.push(cur->left);
            if(cur->right) Q.push(cur->right);            
        }
    }
}

To get width of tree, we can modify node->val of each node to be its serial number in a complete tree. Then for any level, the difference in the val attribute of left most and right most nodes is the width of that level. We can use this to find answer.

 
int widthOfBinaryTree(TreeNode* root) 
{
    int res = 0;
    root->val = 0;
    queue<TreeNode*> Q;
    Q.push(root);
    while(!Q.empty())
    {
        res = max(res, 1+Q.back()->val-Q.front()->val);
        for (int i=Q.size(); i>0; i--)
        {
            TreeNode* cur = Q.front();
            Q.pop();
            if(cur->left) {cur->left->val = 2*cur->val+1; Q.push(cur->left);}
            if(cur->right) {cur->right->val = 2*cur->val+2; Q.push(cur->right);}
        }
    }
    return res;
}

However, this fails for larger tree test cases because of overflow in int. So, we need to track this serial number of node in a separate variable. We can use unsigned long long dtype to track this serial number to avoid overflow issues.

 
int widthOfBinaryTree(TreeNode* root) 
{
    unsigned long long res = 0;
    queue<pair<TreeNode*,unsigned long long>> Q;
    Q.push({root,0});
    while(!Q.empty())
    {
        res = max(res, 1+Q.back().second-Q.front().second);
        for (int i=Q.size(); i>0; i--)
        {
            TreeNode* cur = Q.front().first;
            auto curNum = Q.front().second;
            Q.pop();
            if(cur->left) Q.push({cur->left, 2*curNum+1});
            if(cur->right) Q.push({cur->right, 2*curNum+2});
        }
    }
    return (int)res;
}

TC: $O(n)$, SC:$O(n)$