Maximum Width of Binary Tree in DSA Javascript

Mental Model

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

Analogy: Imagine a theater seating where some seats are empty. The width is the distance from the first occupied seat on the left to the last occupied seat on the right, counting empty seats in between.

       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,null,null,9 -> 6,null,null,null,null,null,null,7

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

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

Level 0: [1(0)]

Why: We assign index 0 to root to track positions

Step 2: Move to level 1: nodes 3 and 2 with indices 1 and 2

Level 1: [3(1)] -> [2(2)]

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

Step 3: Move to level 2: nodes 5 and 9 with indices 3 and 6 (nulls in between)

Level 2: [5(3)] -> null -> null -> [9(6)]

Why: Indices show gaps where null children exist

Step 4: Move to level 3: nodes 6 and 7 with indices 7 and 14 (many nulls between)

Level 3: [6(7)] -> null -> null -> null -> null -> null -> null -> [7(14)]

Why: Indices grow exponentially, capturing position gaps

Step 5: Calculate width per level as last_index - first_index + 1

Widths: Level 0=1, Level 1=2, Level 2=4, Level 3=8

Why: Width counts all positions including nulls between nodes

Step 6: Maximum width found is 8 at level 3

Result: Maximum width = 8

Why: Level 3 has the widest spread including gaps

Result:

Maximum width = 8

Annotated Code

DSA Javascript

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 maxWidth = 0;
  // Queue holds pairs: [node, index]
  const queue = [[root, 0]];

  while (queue.length > 0) {
    const levelLength = queue.length;
    const levelIndices = [];
    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift();
      levelIndices.push(index);
      if (node.left) queue.push([node.left, 2 * index + 1]);
      if (node.right) queue.push([node.right, 2 * index + 2]);
    }
    // Width = last index - first index + 1
    const width = levelIndices[levelIndices.length - 1] - levelIndices[0] + 1;
    if (width > maxWidth) maxWidth = width;
  }
  return maxWidth;
}

// Driver code to build tree and test
const root = new TreeNode(1,
  new TreeNode(3,
    new TreeNode(5,
      new TreeNode(6), null
    ), null
  ),
  new TreeNode(2,
    null,
    new TreeNode(9,
      null,
      new TreeNode(7)
    )
  )
);

console.log(widthOfBinaryTree(root));

const queue = [[root, 0]];

Initialize queue with root node and index 0 to track positions

for (let i = 0; i < levelLength; i++) { const [node, index] = queue.shift();

Process each node in current level with its index

if (node.left) queue.push([node.left, 2 * index + 1]);

Assign left child index as 2*parent_index+1

if (node.right) queue.push([node.right, 2 * index + 2]);

Assign right child index as 2*parent_index+2

const width = levelIndices[levelIndices.length - 1] - levelIndices[0] + 1;

Calculate width of current level including gaps

if (width > maxWidth) maxWidth = width;

Update maximum width if current level is wider

Output

8

Complexity Analysis

Time: O(n) because we visit each node once in a breadth-first manner

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

vs Alternative: Compared to naive approaches that might store full tree structure or use recursion, this uses indexing to efficiently track positions and gaps without extra space for nulls

Edge Cases

Empty tree

Returns 0 as there are no nodes

DSA Javascript

if (!root) return 0;

Tree with only root node

Returns 1 as width is just the root

DSA Javascript

const queue = [[root, 0]];

Tree with single branch (all left or all right)

Width is always 1 since no siblings at any level

DSA Javascript

if (node.left) queue.push([node.left, 2 * index + 1]); if (node.right) queue.push([node.right, 2 * index + 2]);

When to Use This Pattern

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

Common Mistakes

Mistake: Not using indices to track positions, leading to incorrect width when nodes are missing in between
Fix: Assign indices to nodes as if the tree was a complete binary tree to count gaps correctly

Mistake: Calculating width as number of nodes in level instead of distance between leftmost and rightmost nodes
Fix: Calculate width as last_index - first_index + 1 using stored indices

Summary

Finds the maximum width of a binary tree by counting all nodes and gaps between the leftmost and rightmost nodes at each level.

Use when you need to measure the widest spread of nodes in a tree level including empty positions.

The key insight is to assign indices to nodes as if the tree was complete, so gaps are counted in width calculation.