Why Maximum Width of Binary Tree in DSA C++?

The Big Idea

What if you could instantly spot the busiest generation in a family tree without counting each person by hand?

The Scenario

Imagine you have a family tree drawn on paper. You want to know the widest generation -- the one with the most family members side by side. Doing this by counting each level manually is tiring and confusing, especially if the tree is big.

The Problem

Manually counting each level means you must look at every person and remember who belongs to which generation. It's easy to lose track, make mistakes, or take a long time. For big trees, this becomes almost impossible without a systematic way.

The Solution

The "Maximum Width of Binary Tree" method helps you find the widest level quickly by checking all nodes level by level using a queue. It counts how many nodes are at each level and keeps track of the largest count. This way, you get the answer without confusion or errors.

Before vs After

✗ Before

int countWidth(Node* root) {
  // Manually count nodes at each level
  // Hard to track and error-prone
  return 0; // placeholder
}

✓ After

int maxWidth(Node* root) {
  if (!root) return 0;
  std::queue<Node*> q;
  q.push(root);
  int maxWidth = 0;
  while (!q.empty()) {
    int count = q.size();
    maxWidth = std::max(maxWidth, count);
    for (int i = 0; i < count; i++) {
      Node* current = q.front(); q.pop();
      if (current->left) q.push(current->left);
      if (current->right) q.push(current->right);
    }
  }
  return maxWidth;
}

What It Enables

This concept lets you quickly find the widest generation in any tree, helping you understand its shape and balance easily.

Real Life Example

In a company hierarchy, you might want to know which level has the most employees to plan resources better. Using this method, you can find that level fast and accurately.

Key Takeaways

Manual counting is slow and error-prone for wide trees.

Using a queue to check each level simplifies counting nodes.

Maximum width helps understand tree structure and balance.

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