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.

Practice

1. What does the "maximum width" of a binary tree represent?

easy

A. The largest number of nodes present at any single level of the tree

B. The height of the tree from root to the deepest leaf

C. The total number of nodes in the tree

D. The sum of values of all nodes at the widest level

Solution

1. Step 1: Understand the term 'width' in a tree

   The width of a binary tree at a level is the count of nodes present at that level.

2. Step 2: Define maximum width

   The maximum width is the largest such count among all levels.

3. Final Answer:

   The largest number of nodes present at any single level of the tree -> Option A

4. Quick Check:

   Maximum width = max nodes at any level [OK]

Hint: Width means count of nodes at one level, find max count [OK]

Common Mistakes:

• Confusing width with tree height
• Counting total nodes instead of per level
• Summing node values instead of counting nodes

2. Which of the following C++ code snippets correctly declares a queue to store pairs of TreeNode pointers and their indices for width calculation?

easy

A. queue> q;

B. std::queue q;

C. std::queue> q;

D. std::queue> q;

Solution

1. Step 1: Understand queue declaration with pairs

   To store pairs, use std::pair with template parameters inside std::queue<>.

2. Step 2: Check syntax correctness

   std::queue> q; correctly uses std::queue> q; which is valid C++ syntax.

3. Final Answer:

   std::queue> q; -> Option D

4. Quick Check:

   Queue of pairs syntax = std::queue> [OK]

Hint: Use std::pair inside std::queue with angle brackets [OK]

Common Mistakes:

• Missing std::pair<> inside queue
• Incorrect template syntax
• Omitting std:: prefix

3. Given the following binary tree and code snippet, what is the maximum width printed?

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

// Tree structure:
//       1
//      / \
//     2   3
//    /     \
//   4       5

int maxWidth(TreeNode* root) {
  if (!root) return 0;
  std::queue> q;
  q.push({root, 0});
  int maxWidth = 0;
  while (!q.empty()) {
    int size = q.size();
    int start = q.front().second;
    int end = start;
    for (int i = 0; i < size; i++) {
      auto [node, idx] = q.front(); q.pop();
      end = 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, end - start + 1);
  }
  return maxWidth;
}

// Call: maxWidth(root);

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Analyze tree levels and node indices

   Level 0: Node 1 at index 0 (width = 1) Level 1: Nodes 2 (1), 3 (2) width = 2 Level 2: Nodes 4 (3), 5 (6) width = 6 - 3 + 1 = 4

2. Step 2: Calculate maximum width using code logic

   Code calculates width as end - start + 1 per level. Level 2 width is 4, which is maximum.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Max width = 4 nodes at level 2 [OK]

Hint: Track indices per level, width = end - start + 1 [OK]

Common Mistakes:

• Counting nodes without index gaps
• Ignoring index-based width calculation
• Assuming width equals node count only

4. Identify the bug in the following code snippet that attempts to compute the maximum width of a binary tree:

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

medium

A. Not checking if root is nullptr before processing

B. Using q.back().second before popping nodes causes incorrect width calculation

C. Incorrect indexing formula for child nodes

D. Missing return statement at the end

Solution

1. Step 1: Analyze the width calculation timing

   The code calculates width using q.back().second before popping nodes in the current level.

2. Step 2: Identify the bug

   Since q.back() includes nodes from the next level (pushed during previous iteration), width calculation is incorrect.

3. Final Answer:

   Using q.back().second before popping nodes causes incorrect width calculation -> Option B

4. Quick Check:

   Calculate width after popping all nodes at current level [OK]

Hint: Calculate width after processing current level nodes [OK]

Common Mistakes:

• Forgetting root null check
• Misplacing width calculation inside loop
• Wrong child index formulas

5. You want to find the maximum width of a binary tree that may have missing nodes between left and right children at some levels. Which approach correctly handles gaps caused by missing nodes?

hard

A. Use level order traversal with node indices to track positions and calculate width as end - start + 1

B. Count only the number of nodes at each level ignoring their positions

C. Calculate width as the difference between maximum and minimum node values at each level

D. Use depth-first traversal and count nodes recursively without indices

Solution

1. Step 1: Understand the problem with missing nodes

   Missing nodes create gaps, so counting nodes alone misses true width.

2. Step 2: Use indices to track node positions

   Assign indices to nodes as if in a full binary tree to capture gaps, then width = end - start + 1.

3. Final Answer:

   Use level order traversal with node indices to track positions and calculate width as end - start + 1 -> Option A

4. Quick Check:

   Index-based width handles gaps correctly [OK]

Hint: Track node indices to include gaps in width calculation [OK]

Common Mistakes:

• Ignoring gaps by counting nodes only
• Using node values instead of positions
• Using DFS without position tracking