Maximum Width of Binary Tree

🎯

Maximum Width of Binary Tree

mediumTREEAmazonGoogleBloomberg

Imagine you are analyzing a network of connected devices arranged in a hierarchical tree structure, and you want to find the widest level to optimize resource allocation.

💡 This problem requires understanding how to traverse a tree level-by-level and measure the width of each level. Beginners often struggle with how to handle missing nodes and how to correctly calculate width when the tree is sparse.

📋

Problem Statement

Given a binary tree, write a function to find the maximum width of the tree. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), counting the null nodes in between. Return the maximum width among all levels.

The number of nodes in the tree is in the range [1, 10^5].Node values can be any integer.The tree can be very deep and sparse.

💡

Example

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

Output4

The third level has nodes 5,3,null,9. The width is 4 including the null node.

Input"root = [1,3,null,5,3]"

Output2

The second level has nodes 3 and null, width is 2.

• Single node tree → width is 1
• Complete binary tree → width equals number of nodes at last level
• Tree with only left children → width is always 1
• Tree with only right children → width is always 1

⚠️

Common Mistakes

Counting only non-null nodes per level without considering null gaps

Underestimates width, fails on sparse trees

✅ Use indexing to account for null positions

Not normalizing indices leading to integer overflow on deep trees

Runtime errors or incorrect width due to overflow

✅ Normalize indices by subtracting leftmost index at each level

Using DFS without tracking indices properly

Incorrect width calculation or missed nodes

✅ Pass index parameters correctly during DFS traversal

Forgetting to update max width at each level

Final width is incorrect or zero

✅ Update max width after processing each level

🧠

Brute Force (Level Order Traversal with Node Counting)

💡 This approach introduces the fundamental idea of level order traversal and counting nodes per level, which is essential to understand before optimizing. However, it does not handle null gaps, so it underestimates width in sparse trees.

Intuition

Traverse the tree level by level using a queue, count the number of nodes at each level, and track the maximum count.

Algorithm

1. Initialize a queue and add the root node.
2. While the queue is not empty, count the number of nodes at the current level.
3. Update the maximum width if the current level's node count is greater.
4. Add all children of nodes at the current level to the queue.

💡 This approach is straightforward but misses the key detail of counting null nodes between leftmost and rightmost nodes, which affects width calculation.

</>

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = deque([root])  # Initialize queue with root to start BFS
    while queue:
        level_length = len(queue)  # Count nodes at current level
        max_width = max(max_width, level_length)  # Update max width with current level node count
        for _ in range(level_length):
            node = queue.popleft()  # Pop node from front of queue for processing
            if node.left:
                queue.append(node.left)  # Add left child if exists to queue for next level
            if node.right:
                queue.append(node.right)  # Add right child if exists to queue for next level
    return max_width

# Driver code
if __name__ == '__main__':
    # Construct tree [1,3,2,5,3,null,9]
    root = TreeNode(1)
    root.left = TreeNode(3)
    root.right = TreeNode(2)
    root.left.left = TreeNode(5)
    root.left.right = TreeNode(3)
    root.right.right = TreeNode(9)
    print(widthOfBinaryTree(root))  # Output: 3 (does not count null gaps, so underestimates width)

Line Notes

queue = deque([root])Initialize queue with root to start BFS traversal

while queue:Process nodes level by level until no nodes left

level_length = len(queue)Count number of nodes at current level

max_width = max(max_width, level_length)Update max width with current level node count

node = queue.popleft()Pop node from front of queue for processing

if node.left:Add left child if exists to queue for next level

if node.right:Add right child if exists to queue for next level

return max_widthReturn the maximum width found (may underestimate due to ignoring null gaps)

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // Start BFS with root node
        int maxWidth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // Count nodes at current level
            maxWidth = Math.max(maxWidth, levelSize); // Update max width
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll(); // Remove node from queue
                if (node.left != null) queue.offer(node.left); // Add left child
                if (node.right != null) queue.offer(node.right); // Add right child
            }
        }
        return maxWidth; // Return max width (may underestimate)
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        System.out.println(sol.widthOfBinaryTree(root)); // Output: 3 (does not count null gaps)
    }
}

Line Notes

Queue<TreeNode> queue = new LinkedList<>();Initialize queue for BFS traversal

queue.offer(root);Start BFS with root node

while (!queue.isEmpty()) {Process each level until queue is empty

int levelSize = queue.size();Count nodes at current level

maxWidth = Math.max(maxWidth, levelSize);Update max width with current level size

TreeNode node = queue.poll();Remove node from queue for processing

if (node.left != null) queue.offer(node.left);Add left child if present

if (node.right != null) queue.offer(node.right);Add right child if present

return maxWidth;Return the maximum width found (may underestimate)

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

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

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root); // Start BFS with root node
    int maxWidth = 0;
    while (!q.empty()) {
        int levelSize = q.size(); // Count nodes at current level
        maxWidth = max(maxWidth, levelSize); // Update max width
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop(); // Remove node from queue
            if (node->left) q.push(node->left); // Add left child
            if (node->right) q.push(node->right); // Add right child
        }
    }
    return maxWidth; // Return max width (may underestimate)
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);
    cout << widthOfBinaryTree(root) << endl; // Output: 3 (does not count null gaps)
    return 0;
}

Line Notes

queue<TreeNode*> q;Queue to hold nodes for BFS traversal

q.push(root);Start BFS with root node

while (!q.empty()) {Process nodes level by level

int levelSize = q.size();Count nodes at current level

maxWidth = max(maxWidth, levelSize);Update max width with current level size

TreeNode* node = q.front();Get front node from queue

q.pop();Remove node from queue after processing

if (node->left) q.push(node->left);Add left child if exists

if (node->right) q.push(node->right);Add right child if exists

return maxWidth;Return maximum width found (may underestimate)

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function widthOfBinaryTree(root) {
    if (!root) return 0;
    let queue = [root]; // Initialize queue with root for BFS
    let maxWidth = 0;
    while (queue.length > 0) {
        let levelLength = queue.length; // Count nodes at current level
        maxWidth = Math.max(maxWidth, levelLength); // Update max width
        let nextLevel = [];
        for (let i = 0; i < levelLength; i++) {
            let node = queue[i];
            if (node.left) nextLevel.push(node.left); // Add left child
            if (node.right) nextLevel.push(node.right); // Add right child
        }
        queue = nextLevel; // Move to next level nodes
    }
    return maxWidth; // Return max width (may underestimate)
}

// Driver code
const root = new TreeNode(1);
root.left = new TreeNode(3);
root.right = new TreeNode(2);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(9);
console.log(widthOfBinaryTree(root)); // Output: 3 (does not count null gaps)

Line Notes

let queue = [root];Initialize queue with root for BFS traversal

while (queue.length > 0) {Process nodes level by level

let levelLength = queue.length;Count nodes at current level

maxWidth = Math.max(maxWidth, levelLength);Update max width with current level size

for (let i = 0; i < levelLength; i++) {Iterate over all nodes at current level

if (node.left) nextLevel.push(node.left);Add left child if exists

if (node.right) nextLevel.push(node.right);Add right child if exists

queue = nextLevel;Move to next level nodes

return maxWidth;Return maximum width found (may underestimate)

⏱

Complexity

TimeO(n)

SpaceO(n)

We visit each node once in BFS, and queue can hold up to n/2 nodes at the last level.

💡 For n=1000 nodes, this means roughly 1000 operations, which is efficient but does not solve the problem fully because it ignores null gaps.

Interview Verdict: Accepted but incorrect for problem definition

This approach counts nodes per level but ignores null gaps, so it underestimates width when the tree is sparse.

🧠

Better Approach (BFS with Indexing to Track Positions)

💡 This approach introduces the key insight of assigning indices to nodes to measure width including null gaps, bridging the gap between brute force and optimal.

Intuition

Assign an index to each node as if the tree was a complete binary tree, then calculate width as rightmost index - leftmost index + 1 at each level.

Algorithm

1. Initialize a queue with pairs (node, index), starting with (root, 0).
2. For each level, record the index of the first node as leftmost.
3. Traverse all nodes at the level, updating the rightmost index.
4. Calculate width as rightmost - leftmost + 1 and update max width.
5. Add children to queue with indices 2*index and 2*index + 1 respectively.

💡 Indexing nodes simulates a complete binary tree, allowing us to count gaps without storing nulls explicitly.

</>

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 0)])  # (node, index) pairs for BFS
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]  # leftmost index at current level
        for i in range(level_length):
            node, index = queue.popleft()
            index -= first_index  # normalize index to prevent overflow
            if node.left:
                queue.append((node.left, 2 * index))  # left child index
            if node.right:
                queue.append((node.right, 2 * index + 1))  # right child index
            if i == level_length - 1:
                max_width = max(max_width, index + 1)  # update max width
    return max_width

# Driver code
if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(3)
    root.right = TreeNode(2)
    root.left.left = TreeNode(5)
    root.left.right = TreeNode(3)
    root.right.right = TreeNode(9)
    print(widthOfBinaryTree(root))  # Output: 4

Line Notes

queue = deque([(root, 0)])Start BFS with root node at index 0 to track positions

_, first_index = queue[0]Record leftmost index at current level for normalization

index -= first_indexNormalize indices to prevent integer overflow in deep trees

queue.append((node.left, 2 * index))Assign left child index as 2 * parent index

queue.append((node.right, 2 * index + 1))Assign right child index as 2 * parent index + 1

max_width = max(max_width, index + 1)Update max width using normalized rightmost index

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        int maxWidth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int firstIndex = queue.peek().getValue();
            int lastIndex = 0;
            for (int i = 0; i < levelSize; i++) {
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int index = pair.getValue() - firstIndex; // normalize
                if (node.left != null) queue.offer(new Pair<>(node.left, 2 * index));
                if (node.right != null) queue.offer(new Pair<>(node.right, 2 * index + 1));
                if (i == levelSize - 1) lastIndex = index;
            }
            maxWidth = Math.max(maxWidth, lastIndex + 1);
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        System.out.println(sol.widthOfBinaryTree(root)); // Output: 4
    }
}

// Helper Pair class if not using JavaFX or AbstractMap.SimpleEntry
class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) { this.key = key; this.value = value; }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

Line Notes

Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();Queue holds nodes with their indices for BFS traversal

queue.offer(new Pair<>(root, 0));Start BFS with root at index 0

int firstIndex = queue.peek().getValue();Get leftmost index at current level for normalization

int index = pair.getValue() - firstIndex;Normalize index to avoid overflow

queue.offer(new Pair<>(node.left, 2 * index));Assign left child index as 2 * parent index

queue.offer(new Pair<>(node.right, 2 * index + 1));Assign right child index as 2 * parent index + 1

maxWidth = Math.max(maxWidth, lastIndex + 1);Update max width with current level width

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

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

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    unsigned long long maxWidth = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        unsigned long long firstIndex = q.front().second;
        unsigned long long lastIndex = 0;
        for (int i = 0; i < levelSize; i++) {
            auto [node, index] = q.front();
            q.pop();
            index -= firstIndex; // normalize
            if (node->left) q.push({node->left, 2 * index});
            if (node->right) q.push({node->right, 2 * index + 1});
            if (i == levelSize - 1) lastIndex = index;
        }
        maxWidth = max(maxWidth, lastIndex + 1);
    }
    return (int)maxWidth;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);
    cout << widthOfBinaryTree(root) << endl; // Output: 4
    return 0;
}

Line Notes

queue<pair<TreeNode*, unsigned long long>> q;Queue holds nodes with indices for BFS traversal

q.push({root, 0});Start BFS with root at index 0

unsigned long long firstIndex = q.front().second;Get leftmost index at current level for normalization

index -= firstIndex;Normalize index to prevent overflow

q.push({node->left, 2 * index});Assign left child index as 2 * parent index

q.push({node->right, 2 * index + 1});Assign right child index as 2 * parent index + 1

maxWidth = max(maxWidth, lastIndex + 1);Update max width with current level width

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function widthOfBinaryTree(root) {
    if (!root) return 0;
    let queue = [[root, 0]]; // [node, index] pairs for BFS
    let maxWidth = 0;
    while (queue.length > 0) {
        let levelLength = queue.length;
        let firstIndex = queue[0][1]; // leftmost index
        let lastIndex = 0;
        let nextLevel = [];
        for (let i = 0; i < levelLength; i++) {
            let [node, index] = queue[i];
            index -= firstIndex; // normalize
            if (node.left) nextLevel.push([node.left, 2 * index]);
            if (node.right) nextLevel.push([node.right, 2 * index + 1]);
            if (i === levelLength - 1) lastIndex = index;
        }
        maxWidth = Math.max(maxWidth, lastIndex + 1);
        queue = nextLevel;
    }
    return maxWidth;
}

// Driver code
const root = new TreeNode(1);
root.left = new TreeNode(3);
root.right = new TreeNode(2);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(9);
console.log(widthOfBinaryTree(root)); // Output: 4

Line Notes

let queue = [[root, 0]];Initialize queue with root and index 0 for BFS

let firstIndex = queue[0][1];Get leftmost index at current level for normalization

index -= firstIndex;Normalize index to avoid overflow

nextLevel.push([node.left, 2 * index]);Assign left child index as 2 * parent index

nextLevel.push([node.right, 2 * index + 1]);Assign right child index as 2 * parent index + 1

maxWidth = Math.max(maxWidth, lastIndex + 1);Update max width with current level width

queue = nextLevel;Move to next level nodes

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is visited once, and queue holds nodes per level with indices.

💡 For n=1000, this approach efficiently calculates width including gaps.

Interview Verdict: Accepted and correct

This approach correctly handles sparse trees by indexing nodes, making it suitable for interviews.

🧠

Optimal Approach (BFS with Indexing and Integer Normalization)

💡 This approach optimizes memory by normalizing indices at each level to prevent integer overflow in very deep trees.

Intuition

By subtracting the leftmost index at each level from all indices, we keep indices small and avoid overflow while calculating width.

Algorithm

1. Initialize queue with (root, 0).
2. At each level, record the first node's index as offset.
3. For each node, subtract offset from its index to normalize.
4. Add children with indices 2*normalized_index and 2*normalized_index + 1.
5. Calculate width as last normalized index + 1 and update max width.

💡 Normalization keeps indices small and prevents overflow, crucial for large input sizes.

</>

Code

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 0)])
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]
        for i in range(level_length):
            node, index = queue.popleft()
            index -= first_index
            if node.left:
                queue.append((node.left, 2 * index))
            if node.right:
                queue.append((node.right, 2 * index + 1))
            if i == level_length - 1:
                max_width = max(max_width, index + 1)
    return max_width

# Driver code
if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(3)
    root.right = TreeNode(2)
    root.left.left = TreeNode(5)
    root.left.right = TreeNode(3)
    root.right.right = TreeNode(9)
    print(widthOfBinaryTree(root))  # Output: 4

Line Notes

queue = deque([(root, 0)])Start BFS with root at index 0

_, first_index = queue[0]Get leftmost index to normalize

index -= first_indexNormalize index to prevent overflow

queue.append((node.left, 2 * index))Assign left child index

queue.append((node.right, 2 * index + 1))Assign right child index

max_width = max(max_width, index + 1)Update max width with current level width

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));
        int maxWidth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            int firstIndex = queue.peek().getValue();
            int lastIndex = 0;
            for (int i = 0; i < levelSize; i++) {
                Pair<TreeNode, Integer> pair = queue.poll();
                TreeNode node = pair.getKey();
                int index = pair.getValue() - firstIndex;
                if (node.left != null) queue.offer(new Pair<>(node.left, 2 * index));
                if (node.right != null) queue.offer(new Pair<>(node.right, 2 * index + 1));
                if (i == levelSize - 1) lastIndex = index;
            }
            maxWidth = Math.max(maxWidth, lastIndex + 1);
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);
        System.out.println(sol.widthOfBinaryTree(root)); // Output: 4
    }
}

class Pair<K, V> {
    private K key;
    private V value;
    public Pair(K key, V value) { this.key = key; this.value = value; }
    public K getKey() { return key; }
    public V getValue() { return value; }
}

Line Notes

Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();Queue holds nodes with indices for BFS

queue.offer(new Pair<>(root, 0));Start BFS with root at index 0

int firstIndex = queue.peek().getValue();Get leftmost index to normalize

int index = pair.getValue() - firstIndex;Normalize index to prevent overflow

queue.offer(new Pair<>(node.left, 2 * index));Assign left child index

queue.offer(new Pair<>(node.right, 2 * index + 1));Assign right child index

maxWidth = Math.max(maxWidth, lastIndex + 1);Update max width with current level width

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

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

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    unsigned long long maxWidth = 0;
    while (!q.empty()) {
        int levelSize = q.size();
        unsigned long long firstIndex = q.front().second;
        unsigned long long lastIndex = 0;
        for (int i = 0; i < levelSize; i++) {
            auto [node, index] = q.front();
            q.pop();
            index -= firstIndex;
            if (node->left) q.push({node->left, 2 * index});
            if (node->right) q.push({node->right, 2 * index + 1});
            if (i == levelSize - 1) lastIndex = index;
        }
        maxWidth = max(maxWidth, lastIndex + 1);
    }
    return (int)maxWidth;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->right = new TreeNode(2);
    root->left->left = new TreeNode(5);
    root->left->right = new TreeNode(3);
    root->right->right = new TreeNode(9);
    cout << widthOfBinaryTree(root) << endl; // Output: 4
    return 0;
}

Line Notes

queue<pair<TreeNode*, unsigned long long>> q;Queue holds nodes with indices for BFS

q.push({root, 0});Start BFS with root at index 0

unsigned long long firstIndex = q.front().second;Get leftmost index to normalize

index -= firstIndex;Normalize index to prevent overflow

q.push({node->left, 2 * index});Assign left child index

q.push({node->right, 2 * index + 1});Assign right child index

maxWidth = max(maxWidth, lastIndex + 1);Update max width with current level width

class TreeNode {
    constructor(val=0, left=null, right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function widthOfBinaryTree(root) {
    if (!root) return 0;
    let queue = [[root, 0]];
    let maxWidth = 0;
    while (queue.length > 0) {
        let levelLength = queue.length;
        let firstIndex = queue[0][1];
        let lastIndex = 0;
        let nextLevel = [];
        for (let i = 0; i < levelLength; i++) {
            let [node, index] = queue[i];
            index -= firstIndex;
            if (node.left) nextLevel.push([node.left, 2 * index]);
            if (node.right) nextLevel.push([node.right, 2 * index + 1]);
            if (i === levelLength - 1) lastIndex = index;
        }
        maxWidth = Math.max(maxWidth, lastIndex + 1);
        queue = nextLevel;
    }
    return maxWidth;
}

// Driver code
const root = new TreeNode(1);
root.left = new TreeNode(3);
root.right = new TreeNode(2);
root.left.left = new TreeNode(5);
root.left.right = new TreeNode(3);
root.right.right = new TreeNode(9);
console.log(widthOfBinaryTree(root)); // Output: 4

Line Notes

let queue = [[root, 0]];Initialize queue with root and index 0

let firstIndex = queue[0][1];Get leftmost index to normalize

index -= firstIndex;Normalize index to prevent overflow

nextLevel.push([node.left, 2 * index]);Assign left child index

nextLevel.push([node.right, 2 * index + 1]);Assign right child index

maxWidth = Math.max(maxWidth, lastIndex + 1);Update max width with current level width

queue = nextLevel;Move to next level nodes

⏱

Complexity

TimeO(n)

SpaceO(n)

Normalization prevents overflow but does not add complexity; each node is visited once.

💡 This approach is safe for very large trees and is the recommended solution.

Interview Verdict: Accepted and optimal

This is the best practical approach for interviews, handling all edge cases and large inputs safely.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the BFS with indexing and normalization approach in 95% of interviews for correctness and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n)	O(n)	No	N/A	Mention only - does not handle null gaps correctly
2. BFS with Indexing	O(n)	O(n)	No	N/A	Code this for correct width calculation
3. BFS with Indexing and Normalization	O(n)	O(n)	No	N/A	Optimal approach for large/deep trees

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and confirm how width is defined including null nodes.Start with the brute force approach to show understanding of BFS.Explain why brute force fails for sparse trees and introduce indexing.Present the BFS with indexing approach and explain normalization.Code the optimal solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test & Discuss: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of BFS, handling of sparse trees, ability to optimize for large inputs, and clarity in explaining indexing.

Common Follow-ups

• What if the tree is extremely deep? → Use index normalization to avoid overflow.
• Can you solve this using DFS? → Yes, by tracking indices during DFS traversal.

💡 These follow-ups test your ability to adapt the solution to constraints and alternative traversal methods.

🔍

Pattern Recognition

When to Use

1) Problem involves binary tree level properties, 2) Need to measure width or distance between nodes, 3) Null nodes affect measurement, 4) BFS or DFS traversal is applicable.

Signature Phrases

'maximum width of binary tree''length between end-nodes''count null nodes in between'

NOT This Pattern When

Problems that only require node counts per level without gaps or that focus on path sums.

Similar Problems

Binary Tree Level Order Traversal - similar BFS level processingFind Bottom Left Tree Value - uses BFS to find specific node per level

Practice

1. You are given a binary tree and asked to compute the average value of nodes on each level. Which algorithmic approach guarantees an optimal solution that processes nodes level-by-level and efficiently computes these averages?

easy

A. Depth-first search (DFS) without tracking levels, summing all nodes and dividing by total count.

B. Breadth-first search (BFS) using a queue to traverse nodes level-by-level, summing values per level and dividing by the number of nodes at that level.

C. Greedy approach that picks the maximum node value at each level and averages those maximums.

D. Dynamic programming that stores partial sums of subtrees and combines them bottom-up.

Solution

1. Step 1: Understand the problem requires level-wise aggregation

   The problem asks for averages per level, so nodes must be grouped by their depth in the tree.

2. Step 2: Identify BFS as the natural approach for level order traversal

   BFS uses a queue to process nodes level-by-level, allowing summing and counting nodes at each level before moving on.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   BFS naturally groups nodes by level, enabling correct average calculation [OK]

Hint: Level order traversal = BFS with queue [OK]

Common Mistakes:

• Using DFS without level tracking loses level grouping
• Greedy max per level ignores all other nodes
• Bottom-up DP is unnecessary and complex here

2. Consider the following Python code implementing the optimal DFS approach for bottom-up level order traversal. What is the final output when run on the given tree?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrderBottom(root):
    levels = []
    def dfs(node, level):
        if not node:
            return
        if len(levels) == level:
            levels.append([])
        levels[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return levels[::-1]

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(levelOrderBottom(root))

easy

A. [[15, 7], [9, 20], [3]]

B. [[3], [9, 20], [15, 7]]

C. [[9, 20], [3], [15, 7]]

D. [[15, 7], [3], [9, 20]]

Solution

1. Step 1: Trace dfs calls and levels

   Level 0: [3], Level 1: [9, 20], Level 2: [15, 7]

2. Step 2: Reverse levels list before returning

   Reversing [[3], [9, 20], [15, 7]] yields [[15, 7], [9, 20], [3]]

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches bottom-up level order traversal [OK]

Hint: Remember to reverse levels collected by DFS [OK]

Common Mistakes:

• Forgetting to reverse levels
• Mixing up left and right children order

3. What is the time complexity of the optimal BFS with column tracking and ordered map approach for vertical order traversal of a binary tree with n nodes and k distinct columns?

medium

A. O(n log n)

B. O(n)

C. O(n log k)

D. O(k log n)

Solution

1. Step 1: Identify main operations

   Each node is processed once (O(n)). For each node, insertion into ordered map (SortedDict) costs O(log k) where k is number of columns.

2. Step 2: Combine complexities

   Total time is O(n) * O(log k) = O(n log k). Sorting all nodes (O(n log n)) is avoided here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Ordered map insertion dominates, giving O(n log k) [OK]

Hint: Ordered map insertion per node costs log k, not log n [OK]

Common Mistakes:

• Assuming O(n) ignoring map insertion cost
• Confusing k (columns) with n (nodes) in complexity

4. What is the time complexity of the optimal two-stacks zigzag level order traversal algorithm for a binary tree with n nodes?

medium

A. O(n), since each node is visited exactly once and pushed/popped at most twice

B. O(n^2), because pushing children in two stacks doubles the work per node

C. O(n log n), because each level requires reversing the node list

D. O(n), but with O(h) auxiliary space where h is the tree height due to recursion stack

Solution

1. Step 1: Identify node visits

   Each node is pushed and popped exactly once per stack, total constant times per node.

2. Step 2: Analyze operations per node

   Appending children and popping nodes are O(1) operations, no nested loops over nodes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear traversal with constant work per node -> O(n) time [OK]

Hint: Each node processed once, no repeated work [OK]

Common Mistakes:

• Assuming reversing adds O(n log n)
• Confusing stack pushes as doubling work

5. Suppose the binary tree nodes can be dynamically added or removed during traversal, or the tree is extremely deep (height > 10^5). Which modification to the level order traversal algorithm is most appropriate to handle these constraints efficiently?

hard

A. Use the recursive DFS with level tracking approach as is, since it handles all cases optimally.

B. Switch to an iterative BFS approach using a queue to avoid recursion stack overflow and handle dynamic changes.

C. Use a naive recursive approach without level tracking and sort nodes by level after traversal.

D. Use a depth-limited DFS that stops at a fixed depth to avoid deep recursion.

Solution

1. Step 1: Identify issues with recursive DFS on very deep trees

   Recursive DFS risks stack overflow on very deep trees and does not handle dynamic changes well.

2. Step 2: Evaluate iterative BFS suitability

   Iterative BFS with a queue avoids recursion stack issues and can handle dynamic node additions/removals during traversal.

3. Step 3: Discard naive and depth-limited approaches

   Naive recursion and sorting is inefficient; depth-limited DFS misses nodes beyond limit.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Iterative BFS is robust for deep or dynamic trees [OK]

Hint: Iterative BFS avoids recursion limits and handles dynamic trees [OK]

Common Mistakes:

• Assuming recursion always works
• Ignoring stack overflow risk
• Using depth limits that lose nodes