https://leetcode.com/problems/maximum-width-of-binary-tree/description/

#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 void inOrder(TreeNode* root)
{
    if (!root)
        return;

    if (root->left)
        inOrder(root->left);
    cout << root->val << "\n";
    if (root->right)
        inOrder(root->right);
}

void preOrder(TreeNode* root)
{
    if (!root)
        return;

    cout << root->val;
    cout << "\n";
    if (root->left)
        preOrder(root->left);
    if (root->right)
        preOrder(root->right);
}

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) {
            return 0;
        }
        /*traverse tree and lebel each node with level order*/
        return getLevelOrder(root);
    }

    int getLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        root->val = 0;
        queue<int> buckets[32];
        unsigned int num = 0;
        int level = 0;
        int maxWidth = 1;
        buckets[0].push(root->val);      
        while (!q.empty()) {
            TreeNode* p = q.front();
            q.pop();
            if (p->left) {
                num = p->left->val = 2 * p->val + 1;
                level = getLevel(num + 1);
                buckets[level].push(num);
                q.push(p->left);            
            }
            if (p->right) {
                num = p->right->val = 2 * p->val + 2;
                level = getLevel(num + 1);
                buckets[level].push(num);
                q.push(p->right);
            }
        }  

        for (int i = 0; i <= level; i++) {
            int width = buckets[i].back() - buckets[i].front() + 1;
            if (width > maxWidth)
                maxWidth = width;
        }
        return maxWidth;    
    }
    int getLevel(unsigned int levelOrder) {
        int level = 0;
        while (levelOrder) {
            levelOrder >>= 1;
            level++;
        }
        return level - 1;
    }
};

int main()
{
    int input[] = {1,3,2,5,3,-1,9};
    //int input[] = {1};
    int size = sizeof(input) / sizeof(int);
    //cout << "size = " << size << "\n";

    TreeNode **Tree = new TreeNode*[size];

    for (int i = size - 1; i >= 0; i--) {
        if (input[i] != -1) {
            Tree[i] = new TreeNode(input[i]);
            int lChild = 2 * i + 1;
            int rChild = 2 * i + 2;
            Tree[i]->val = input[i];
            if (lChild < size && (input[lChild] != -1)) {
                Tree[i]->left  = Tree[lChild];
            }
            if (rChild < size && (input[rChild] != -1)) {
                Tree[i]->right  = Tree[rChild];
            }
        }
    }
 
    //cout << "preOrder\n";
    //preOrder(Tree[0]);
    //cout << "end\n\n";

    //cout << "inOrder\n";
    //inOrder(Tree[0]);
    //cout << "end\n\n";
 
    Solution solution;
    int width = solution.widthOfBinaryTree(Tree[0]);
    cout << "width = " << width << "\n";
}