Skip to main content

Maximum Width of Binary Tree

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    int widthOfBinaryTree(TreeNode* root) {
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});
        int ans = 0;
        while (!q.empty()) {
            int n = q.size();
            int start = q.front().second;
            int end = q.back().second;
            ans = max(ans, end - start + 1);
            for (int i = 0; i < n; i++) {
                TreeNode* node = q.front().first;
                int p = q.front().second;
                q.pop();
                if (node->left != NULL) {
                    q.push({node->left, (long long)2 * p + 1});
                }
                if (node->right != NULL) {
                    q.push({node->right, (long long)2 * p + 2});
                }
            }
        }
        return ans;
    }
};