Maximum Width of Binary Tree in DSA C++ - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: Imagine you are working with a family tree app that shows generations of family members. You want to find out the widest generation -- the one with the most members lined up horizontally.

🎯 Goal: Build a program that calculates the maximum width of a binary tree. The width is the number of nodes between the leftmost and rightmost non-null nodes at any level, including nulls in between.

📋 What You'll Learn

Create a binary tree node structure with integer values

Build a sample binary tree with given nodes

Use a breadth-first search approach with position indexing

Calculate the maximum width of the tree

Print the maximum width as the final output

💡 Why This Matters

🌍 Real World

Calculating the maximum width of a binary tree helps in understanding the breadth of hierarchical data, such as family trees, organizational charts, or file directory structures.

💼 Career

This concept is useful for software engineers working on tree data structures, UI layout engines, and algorithms that require breadth analysis of hierarchical data.

1

Create the Binary Tree Node Structure and Sample Tree

Create a struct called TreeNode with an int val, and two pointers left and right to TreeNode. Then create a binary tree with root node value 1, root's left child value 3, root's right child value 2, root's left child's left child value 5, and root's left child's right child value 3.

DSA C++

// Your code here to define TreeNode and create the tree

Hint

Define a struct with a constructor for easy node creation. Then link nodes to form the tree.

2

Add a Queue and Position Indexing Setup

Include the queue and utility headers. Create a queue of pairs called q that stores TreeNode* and unsigned long long for position indexing. Push the root node with position 0 into q.

DSA C++

#include 
#include 

// Your code here to create queue and push root with position 0

Hint

Use a queue to hold nodes with their horizontal positions starting at 0 for the root.

3

Calculate the Maximum Width Using Level Order Traversal

Write a while loop that runs while q is not empty. Inside, get the size of q as level_size. Store the position of the first node in the level as level_head_index. Iterate level_size times, popping from q. For each node, get its position pos and normalize it by subtracting level_head_index. If the node has a left child, push it with position 2 * pos + 1. If the node has a right child, push it with position 2 * pos + 2. Track the last node's normalized position as level_tail_index. Update an integer variable max_width with the maximum of itself and level_tail_index - level_head_index + 1. Initialize max_width to 0 before the loop.

DSA C++

int max_width = 0;
// Your code here to calculate max_width using level order traversal

Hint

Use a queue to traverse level by level. Normalize positions to avoid overflow. Update max_width with the width of each level.

4

Print the Maximum Width

Add a cout statement to print the value of max_width followed by a newline.

DSA C++

cout << max_width << endl;  // Print the maximum width

Hint

Print the final maximum width after processing all levels.

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