Maximum Width of Binary Tree - Practice Coding Problems

Maximum Width of Binary Tree - Problem

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will be in the range of a 32-bit signed integer.

Input & Output

Example 1 — Standard Tree

$ Input: root = [1,3,2,5,3,null,9]

› Output: 4

💡 Note: At level 3, we have nodes 5, 3, and 9. In a complete binary tree representation, positions would be 0, 1, and 3, giving width = 3 - 0 + 1 = 4

Example 2 — Skewed Tree

$ Input: root = [1,3,2,5,null,null,9,6,null,7]

› Output: 7

💡 Note: At the deepest level, nodes 6 and 7 span from position 0 to position 6 in the complete tree representation, giving width = 6 - 0 + 1 = 7

Example 3 — Single Node

$ Input: root = [1]

› Output: 1

💡 Note: Tree has only root node, so maximum width is 1

Constraints

The number of nodes in the tree is in the range [1, 3000]
-100 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with array representation [1,3,2,5,3,null,9]

Level Analysis

Calculate width for each level using position indices

Maximum Width

Return the largest width found: 4

Key Takeaway

🎯 Key Insight: Assign position indices to nodes using binary tree properties and calculate width as the span between leftmost and rightmost positions at each level

Asked in

F Facebook 25 G Google 18 A Amazon 12 M Microsoft 8

The key insight is to use BFS with position tracking where each node gets a position index based on binary tree properties (left child = 2*parent, right child = 2*parent+1). The optimal approach uses position normalization to prevent integer overflow. Time: O(n), Space: O(w) where w is maximum width.

Common Approaches

Approach	Time	Space	Notes
✓ Level Order with Full Position Tracking	O(n)	O(w)	Store all possible positions for each level and find the span
BFS with Position Normalization	O(n)	O(w)	Use BFS with normalized positions to prevent overflow

Level Order with Full Position Tracking — Algorithm Steps

Traverse tree level by level using BFS
For each level, store positions of all nodes
Calculate width as rightmost_pos - leftmost_pos + 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start BFS with root at position 0

Track Positions

For each level, store all node positions

Calculate Width

Width = rightmost_pos - leftmost_pos + 1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct NodePos {
    struct TreeNode* node;
    int pos;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    int maxWidth = 0;
    struct NodePos queue[10000];
    int front = 0, rear = 0;
    
    queue[rear++] = (struct NodePos){root, 0};
    
    while (front < rear) {
        int levelSize = rear - front;
        int levelPositions[1000];
        int posCount = 0;
        
        for (int i = 0; i < levelSize; i++) {
            struct NodePos current = queue[front++];
            levelPositions[posCount++] = current.pos;
            
            if (current.node->left) {
                queue[rear++] = (struct NodePos){current.node->left, 2 * current.pos};
            }
            if (current.node->right) {
                queue[rear++] = (struct NodePos){current.node->right, 2 * current.pos + 1};
            }
        }
        
        if (posCount > 0) {
            int width = levelPositions[posCount - 1] - levelPositions[0] + 1;
            if (width > maxWidth) {
                maxWidth = width;
            }
        }
    }
    
    return maxWidth;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    // Simple parsing for [1,3,2,5,3,null,9]
    struct TreeNode* root = createNode(1);
    root->left = createNode(3);
    root->right = createNode(2);
    root->left->left = createNode(5);
    root->left->right = createNode(3);
    root->right->right = createNode(9);
    
    int result = solution(root);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Visit each node once in BFS traversal

✓ Linear Growth

Space Complexity

O(w)

Queue stores at most w nodes where w is maximum width

✓ Linear Space

87.0K Views

Medium Frequency

~25 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Level Order with Full Position Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler