Maximum Width of Binary Tree in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the function that calculates the maximum width of a binary tree.

DSA C++

int [1](TreeNode* root);

Drag options to blanks, or click blank then click option'

AmaxWidth

BmaxDepth

CmaxHeight

DmaxSize

Attempts:

3 left

💡 Hint

Common Mistakes

Using maxDepth or maxHeight which relate to tree height, not width.

Using generic names like maxSize that don't specify width.

The function name should be maxWidth as it clearly indicates the purpose of calculating the maximum width of the binary tree.

2fill in blank

medium

Complete the code to initialize the queue for level order traversal.

DSA C++

std::queue<std::pair<TreeNode*, unsigned long long>> [1];

Drag options to blanks, or click blank then click option'

Astack

Bq

Clist

Dvec

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'stack' which is a different data structure.

Using 'list' or 'vec' which are not queues.

The queue variable is commonly named 'q' for queue, which is used for level order traversal.

3fill in blank

hard

Fix the error in the loop condition to process nodes level by level.

DSA C++

while (![1].empty()) {

Drag options to blanks, or click blank then click option'

Astack

Bqueue

Cq

Dlist

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'queue' which is the type, not the variable name.

Using 'stack' or 'list' which are not the queue variable.

The queue variable is named 'q', so the loop should check if 'q' is not empty to continue processing.

4fill in blank

hard

Fill both blanks to correctly calculate the width of the current level.

DSA C++

unsigned long long width = last - [1] + 1;
maxWidth = std::max(maxWidth, width[2]);

Drag options to blanks, or click blank then click option'

Afirst

B+

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition when calculating width.

Using wrong variable names or operators.

Width is calculated as last - first + 1. Then maxWidth is updated with the maximum of current maxWidth and width + 0 (width itself).

5fill in blank

hard

Fill all three blanks to correctly push child nodes into the queue with updated indices.

DSA C++

if (node->left) q.push({node->left, [1] * 2});
if (node->right) q.push({node->right, [2] * 2 [3] 1});

Drag options to blanks, or click blank then click option'

Aindex

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition for right child index.

Using wrong variable names.

For left child, index is doubled. For right child, index is doubled and incremented by 1.

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