Maximum Width of Binary Tree in DSA Java

Mental Model

We want to find the widest level in a tree by counting nodes between the leftmost and rightmost nodes at each level, including gaps.

Analogy: Imagine a tree as a family photo where some people are missing. The width is the distance from the first person on the left to the last person on the right, counting empty spots too.

       1
      / \
     3   2
    /     \
   5       9
  /         \
 6           7

Levels:
Level 0: 1
Level 1: 3 -> 2
Level 2: 5 -> null -> null -> 9
Level 3: 6 -> null -> null -> null -> null -> null -> null -> 7

Dry Run Walkthrough

Input: Binary tree: 1 -> 3, 2 -> 5, 9 -> 6, 7 as shown in mental model

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

Step 1: Start at root (1) with index 0 in queue

[ (1,0) ]

Why: We assign index 0 to root to track positions for width calculation

Step 2: Process level 0: only node 1 at index 0

Level nodes: (1,0)
Width = 0 - 0 + 1 = 1

Why: Width is rightmost index minus leftmost plus one

Step 3: Add children of 1: left child 3 at index 1, right child 2 at index 2

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

Why: Left child index = 2*parent_index + 1, right child = 2*parent_index + 2

Step 4: Process level 1: nodes 3 at index 1 and 2 at index 2

Level nodes: (3,1), (2,2)
Width = 2 - 1 + 1 = 2

Why: Width includes all nodes between leftmost and rightmost indices

Step 5: Add children: 3's left child 5 at index 3, 2's right child 9 at index 6

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

Why: Indices reflect positions including gaps for missing nodes

Step 6: Process level 2: nodes 5 at index 3 and 9 at index 6

Level nodes: (5,3), (9,6)
Width = 6 - 3 + 1 = 4

Why: Width counts null gaps between nodes 5 and 9

Step 7: Add children: 5's left child 6 at index 7, 9's right child 7 at index 14

[ (6,7), (7,14) ]

Why: Indices continue doubling pattern to track positions

Step 8: Process level 3: nodes 6 at index 7 and 7 at index 14

Level nodes: (6,7), (7,14)
Width = 14 - 7 + 1 = 8

Why: Maximum width found at this level including gaps

Result:

Maximum width = 8

Annotated Code

DSA Java

import java.util.*;

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

public class MaxWidthBinaryTree {
    public static int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int maxWidth = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0));

        while (!queue.isEmpty()) {
            int size = queue.size();
            int minIndex = queue.peek().getValue(); // leftmost index at current level
            int first = 0, last = 0;
            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> p = queue.poll();
                TreeNode node = p.getKey();
                int index = p.getValue() - minIndex; // normalize to prevent overflow
                if (i == 0) first = index;
                if (i == size - 1) last = index;
                if (node.left != null) queue.offer(new Pair<>(node.left, 2 * index + 1));
                if (node.right != null) queue.offer(new Pair<>(node.right, 2 * index + 2));
            }
            maxWidth = Math.max(maxWidth, last - first + 1);
        }
        return maxWidth;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.right.right = new TreeNode(9);
        root.left.left.left = new TreeNode(6);
        root.right.right.right = new TreeNode(7);

        System.out.println(widthOfBinaryTree(root));
    }
}

// Helper Pair class for Java 8 and below
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; }
}

queue.offer(new Pair<>(root, 0));

Start BFS with root at index 0 to track positions

int minIndex = queue.peek().getValue();

Get leftmost index at current level to normalize indices

int index = p.getValue() - minIndex;

Normalize index to avoid integer overflow and keep relative positions

if (node.left != null) queue.offer(new Pair<>(node.left, 2 * index + 1));

Assign left child index based on parent's normalized index

if (node.right != null) queue.offer(new Pair<>(node.right, 2 * index + 2));

Assign right child index similarly

maxWidth = Math.max(maxWidth, last - first + 1);

Update maximum width found so far

Output

8

Complexity Analysis

Time: O(n) because we visit each node once during level order traversal

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

vs Alternative: Compared to naive methods that might store all nodes with gaps explicitly, this approach uses index math to track positions efficiently without extra space for nulls

Edge Cases

Empty tree

Returns 0 as width since no nodes exist

DSA Java

if (root == null) return 0;

Single node tree

Returns 1 as width since only root exists

DSA Java

queue.offer(new Pair<>(root, 0));

Tree with only left children

Width is always 1 at each level

DSA Java

if (node.left != null) queue.offer(new Pair<>(node.left, 2 * index + 1));

When to Use This Pattern

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

Common Mistakes

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

Mistake: Counting only existing nodes ignoring gaps, leading to incorrect width
Fix: Use indices to count gaps between leftmost and rightmost nodes

Summary

Finds the maximum width of a binary tree by tracking node positions at each level.

Use when you need to measure the widest level including gaps in a binary tree.

The key is assigning indices to nodes to count gaps and normalize to avoid overflow.

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 definition of width in a binary tree

   The width is the count of nodes at a particular level in the tree.

2. Step 2: Identify 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 [OK]

Common Mistakes:

• Confusing width with tree height
• Thinking width is sum of node values
• Counting total nodes instead of per level

2. Which Java data structure is most suitable to track nodes level by level when finding maximum width of a binary tree?

easy

A. Stack

B. HashMap

C. Queue

D. ArrayList

Solution

1. Step 1: Identify traversal method for level order

   Level order traversal uses a queue to process nodes level by level.

2. Step 2: Choose data structure

   A queue allows nodes to be added and removed in FIFO order, perfect for level traversal.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level order traversal to measure width [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Choosing HashMap which doesn't preserve order
• Using ArrayList without queue behavior

3. What is the output of the following Java code snippet that calculates maximum width of a binary tree?

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

// Tree structure:
//       1
//      / \
//     2   3
//    /     \
//   4       5

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);

// Maximum width calculation
int maxWidth = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  int size = queue.size();
  maxWidth = Math.max(maxWidth, size);
  for (int i = 0; i < size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}
System.out.println(maxWidth);

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze tree levels and node counts

   Level 1 has 1 node (1), level 2 has 2 nodes (2,3), level 3 has 2 nodes (4,5).

2. Step 2: Determine maximum width

   The maximum number of nodes at any level is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at level 2 [OK]

Hint: Count nodes per level, max is answer [OK]

Common Mistakes:

• Counting total nodes instead of per level
• Assuming level 3 has 3 nodes incorrectly
• Ignoring null children in width calculation

4. Identify the bug in this Java code snippet that attempts to find the maximum width of a binary tree:

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int maxWidth = 0;
while (!queue.isEmpty()) {
  int size = queue.size();
  maxWidth = Math.max(maxWidth, size);
  for (int i = 0; i <= size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}

medium

A. The loop condition should be i < size, not i <= size

B. The queue should be a Stack instead

C. maxWidth should be updated after the for loop

D. The root node is never added to the queue

Solution

1. Step 1: Check the for loop iteration count

   The loop runs from i = 0 to i <= size, which means it runs size+1 times, causing an extra poll.

2. Step 2: Correct the loop condition

   It should run exactly size times, so condition must be i < size.

3. Final Answer:

   The loop condition should be i < size, not i <= size -> Option A

4. Quick Check:

   Loop must run size times exactly [OK]

Hint: Use i < size for loops over queue size [OK]

Common Mistakes:

• Using <= instead of < in for loop
• Replacing queue with stack incorrectly
• Updating maxWidth at wrong place

5. Given a binary tree where some nodes are missing children, how can you modify the maximum width calculation to include null positions between nodes, so the width counts the distance between the leftmost and rightmost non-null nodes at each level? Choose the best approach.

hard

A. Calculate width by summing values of nodes at each level

B. Count only non-null nodes at each level ignoring positions

C. Use a stack to store nodes and count them

D. Assign an index to each node as if the tree was a complete binary tree, track min and max indices per level, width = max - min + 1

Solution

1. Step 1: Understand the problem with missing nodes

   Simple counting misses gaps caused by null children, so width is underestimated.

2. Step 2: Use indexing to simulate complete tree positions

   Assign indices to nodes as in a complete binary tree (root=0, left=2*index, right=2*index+1).

3. Step 3: Calculate width per level using min and max indices

   Width = max index - min index + 1, capturing gaps between nodes.

4. Final Answer:

   Assign an index to each node as if the tree was a complete binary tree, track min and max indices per level, width = max - min + 1 -> Option D

5. Quick Check:

   Indexing nodes captures gaps for accurate width [OK]

Hint: Use node indices to count gaps for true width [OK]

Common Mistakes:

• Ignoring null gaps between nodes
• Counting only non-null nodes without positions
• Using stack instead of queue for level traversal