Maximum Width of Binary Tree in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation

What is the output of the following C++ code that calculates the maximum width of a binary tree?

DSA C++

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

#include <iostream>
#include <queue>
#include <algorithm>

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    unsigned long long maxWidth = 0;
    std::queue<std::pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int size = q.size();
        unsigned long long left = q.front().second;
        unsigned long long right = left; // initialize right
        for (int i = 0; i < size; i++) {
            auto node = q.front().first;
            unsigned long long idx = q.front().second - left;
            q.pop();
            right = idx;
            if (node->left) q.push({node->left, 2 * idx + 1});
            if (node->right) q.push({node->right, 2 * idx + 2});
        }
        maxWidth = std::max(maxWidth, right + 1);
    }
    return static_cast<int>(maxWidth);
}

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);
    std::cout << widthOfBinaryTree(root) << std::endl;
    return 0;
}

A 2

B 3

C 4

D 5

💡 Hint

Think about how the width is calculated including null nodes between the leftmost and rightmost nodes at each level.

The maximum width is calculated by indexing nodes as if the tree was a complete binary tree. The maximum width here is 4 at the last level (nodes 5, 3, null, 9).

🧠 Conceptual

intermediate

Understanding Indexing in Maximum Width Calculation

In the maximum width calculation of a binary tree, why do we subtract the leftmost index from all node indices at the current level before processing?

A To skip null nodes and only count existing nodes

B To prevent integer overflow by normalizing indices to start from zero at each level

C To count only the nodes that have children at the current level

D To ensure the indices are always even numbers

💡 Hint

Consider what happens to indices as the tree depth increases.

Subtracting the leftmost index normalizes indices to start from zero at each level, preventing very large numbers that could cause overflow.

🔧 Debug

advanced

Identify the Bug in Width Calculation Code

What error will the following code produce when calculating the maximum width of a binary tree?

DSA C++

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    unsigned long long maxWidth = 0;
    std::queue<std::pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int size = q.size();
        unsigned long long left = q.front().second;
        unsigned long long right = 0;
        for (int i = 0; i < size; i++) {
            auto node = q.front().first;
            unsigned long long idx = q.front().second;
            q.pop();
            right = idx;
            if (node->left) q.push({node->left, 2 * idx + 1});
            if (node->right) q.push({node->right, 2 * idx + 2});
        }
        maxWidth = std::max(maxWidth, right - left + 1);
    }
    return static_cast<int>(maxWidth);
}

A Integer overflow error due to large indices without normalization

B No error, code runs correctly and returns max width

C Runtime error due to accessing null pointer

D Compilation error due to missing header files

💡 Hint

Look at how indices are handled inside the loop.

Indices grow exponentially with tree depth. Without subtracting the leftmost index, they can become very large causing overflow.

🚀 Application

advanced

Maximum Width of a Sparse Binary Tree

Given a sparse binary tree where many nodes are missing, which approach correctly calculates the maximum width including null nodes between leftmost and rightmost nodes?

A Use DFS and calculate width by counting leaf nodes only

B Use DFS and count only existing nodes at each level

C Use BFS but ignore null nodes and count only present nodes

D Use BFS with node indices normalized by subtracting the leftmost index at each level

💡 Hint

Think about how to include gaps caused by missing nodes.

BFS with normalized indices tracks positions including gaps, allowing correct width calculation even in sparse trees.

❓ Predict Output

expert

Output of Maximum Width for a Complex Tree

What is the output of the following code that calculates the maximum width of this binary tree?

DSA C++

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

#include <iostream>
#include <queue>
#include <algorithm>

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    unsigned long long maxWidth = 0;
    std::queue<std::pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int size = q.size();
        unsigned long long left = q.front().second;
        unsigned long long right = left;
        for (int i = 0; i < size; i++) {
            auto node = q.front().first;
            unsigned long long idx = q.front().second - left;
            q.pop();
            right = idx;
            if (node->left) q.push({node->left, 2 * idx + 1});
            if (node->right) q.push({node->right, 2 * idx + 2});
        }
        maxWidth = std::max(maxWidth, right + 1);
    }
    return static_cast<int>(maxWidth);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->right->right = new TreeNode(5);
    root->left->left->left = new TreeNode(6);
    root->right->right->right = new TreeNode(7);
    std::cout << widthOfBinaryTree(root) << std::endl;
    return 0;
}

A 8

B 4

C 5

D 6

💡 Hint

Consider the indexing of nodes including null gaps at the deepest level.

The maximum width is 8 at the last level, counting nodes 6, nulls, and 7 as if the tree was complete.