Maximum Width of Binary Tree

Given a binary tree, write a function to get 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 in the level, where the null nodes between the end-nodes are also counted into the length calculation.

It is guaranteed that the answer will in the range of 32-bit signed integer.

Example:

Input: 

           1
         /   \
        3     2
       / \     \  
      5   3     9 

Output: 4
Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9).

Approach:

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int widthOfBinaryTree(TreeNode *root)
{

    deque<pair<TreeNode *, size_t>> queue(1, {root, 0});
    int maxTreeWidth{0};
    while (!queue.empty())
    {
        int levelWidth = queue.back().second -
        queue.front().second + 1;
        if (levelWidth > maxTreeWidth)
            maxTreeWidth = levelWidth;
        for (int count = queue.size(), i{0}; i < count; i++)
        {
            auto node = queue.front();
            TreeNode *qNode = node.first;
            queue.pop_front();
            if (qNode->left)
                queue.push_back({qNode->left, 2 * node.second});
            if (qNode->right)
                queue.push_back({qNode->right, 2 * 
                  node.second + 1});
        }
    }
    return maxTreeWidth;
}

int main()
{

    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);

    cout << widthOfBinaryTree(root);

    return 0;
}