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.