class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root)
            return 0;

        queue<pair<TreeNode*, uint>> q;
        q.push(make_pair(root, 0));

        uint width = 0;
        while (!q.empty()) {
            int size_q = q.size();

            uint lo = q.front().second;
            uint hi = q.front().second;
            while (size_q--) {
                TreeNode* cur = q.front().first;
                uint id = q.front().second;
                q.pop();

                hi = id;
                if (cur->left) q.push(make_pair(cur->left, id*2 + 1));
                if (cur->right) q.push(make_pair(cur->right, id*2 + 2));
            }

            width = max(width, hi - lo + 1);
        }

        return width;
    }
};