Maximum Width of Binary Tree in DSA C++

Mental Model

We want to find the widest level in a tree, counting all nodes including gaps between them.

Analogy: Imagine a family tree where some branches have missing members; the width counts all spots from leftmost to rightmost member, even if some are empty.

       1
      / \
     2   3
    /     \
   4       5

Levels:
Level 0: 1
Level 1: 2 -> 3
Level 2: 4 -> null -> null -> 5

Dry Run Walkthrough

Input: Binary tree: root=1, left=2, right=3, 2's left=4, 3's right=5

Goal: Find the maximum width among all levels, counting nulls between nodes

Step 1: Start at root level, enqueue (node=1, index=0)

[ (1,0) ]

Why: We assign index 0 to root to track positions

Step 2: Process level 0: nodes [(1,0)], width = 0 - 0 + 1 = 1

[ (2,1), (3,2) ]

Why: Add children with indices: left=2*0+1=1, right=2*0+2=2

Step 3: Process level 1: nodes [(2,1), (3,2)], width = 2 - 1 + 1 = 2

[ (4,3), (5,6) ]

Why: Add children: 2's left=2*1+1=3, 3's right=2*2+2=6; missing children skipped

Step 4: Process level 2: nodes [(4,3), (5,6)], width = 6 - 3 + 1 = 4

[]

Why: No more children, end traversal

Result:

Maximum width is 4 at level 2
Level 2: 4 -> null -> null -> 5

Annotated Code

DSA C++

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

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

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    unsigned long long maxWidth = 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int size = q.size();
        unsigned long long start = q.front().second;
        unsigned long long end = q.back().second;
        maxWidth = max(maxWidth, end - start + 1);
        for (int i = 0; i < size; i++) {
            auto nodePair = q.front(); q.pop();
            TreeNode* node = nodePair.first;
            unsigned long long idx = nodePair.second - start; // normalize to prevent overflow
            if (node->left) q.push({node->left, 2 * idx + 1});
            if (node->right) q.push({node->right, 2 * idx + 2});
        }
    }
    return (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);

    cout << widthOfBinaryTree(root) << "\n";
    return 0;
}

q.push({root, 0});

Start BFS with root at index 0 to track positions

unsigned long long start = q.front().second;

Record leftmost index at current level

unsigned long long end = q.back().second;

Record rightmost index at current level

maxWidth = max(maxWidth, end - start + 1);

Update max width using indices difference

unsigned long long idx = nodePair.second - start;

Normalize indices to prevent overflow

if (node->left) q.push({node->left, 2 * idx + 1});

Assign left child index based on current node

if (node->right) q.push({node->right, 2 * idx + 2});

Assign right child index based on current node

Output

4

Complexity Analysis

Time: O(n) because we visit each node once in BFS

Space: O(n) because queue can hold up to all nodes at the widest level

vs Alternative: Naive approach counting nodes per level without indices misses gaps, so this method is more accurate and efficient

Edge Cases

Empty tree

Returns 0 width

DSA C++

if (!root) return 0;

Single node tree

Returns width 1

DSA C++

maxWidth = max(maxWidth, end - start + 1);

Tree with missing children creating gaps

Correctly counts width including null gaps

DSA C++

unsigned long long idx = nodePair.second - start;

When to Use This Pattern

When asked for the widest level in a tree including gaps, use BFS with position indices to track node positions and calculate width.

Common Mistakes

Mistake: Not normalizing indices causing integer overflow
Fix: Subtract start index from all indices at each level to keep them small

Mistake: Counting only existing nodes ignoring gaps
Fix: Use indices to count width including null positions

Summary

Finds the maximum width of a binary tree counting all nodes including gaps.

Use when you need to measure the widest level including empty spots in a tree.

Track node positions with indices during BFS to calculate width accurately.

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