Maximum Width of Binary Tree in DSA Typescript

Mental Model

We want to find the widest level in a tree by counting nodes including gaps between them.

Analogy: Imagine a tree as a family photo where some people are missing but their spots remain empty; the width counts all spots from leftmost to rightmost person including empty spots.

       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: 1 -> 2, 3 -> 4 (left child of 2), 5 (right child of 3)

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

Step 1: Start at root (level 0), assign index 0

Level 0: [0]1
Width = 1 (only one node)

Why: We begin counting from the root with index 0 to track positions

Step 2: Move to level 1, assign indices: left child 2 -> 0*2=0, right child 3 -> 0*2+1=1

Level 1: [0]2 -> [1]3
Width = 2 (nodes at indices 0 and 1)

Why: Indices help us count gaps between nodes even if some are missing

Step 3: Move to level 2, assign indices for children: 4 (left child of 2) -> 0*2=0, no right child of 2, no left child of 3, 5 (right child of 3) -> 1*2+1=3

Level 2: [0]4 -> null -> null -> [3]5
Width = 4 (indices 0 to 3)

Why: Counting indices including null spots shows the true width

Result:

Maximum width is 4 at level 2
Level 2: 4 -> null -> null -> 5

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let maxWidth = 0;
  // Queue holds pairs of node and its index
  const queue: Array<[TreeNode, number]> = [[root, 0]];

  while (queue.length > 0) {
    const levelLength = queue.length;
    const levelIndices = queue.map(pair => pair[1]);
    const levelMin = levelIndices[0];
    const levelMax = levelIndices[levelIndices.length - 1];
    maxWidth = Math.max(maxWidth, levelMax - levelMin + 1);

    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift()!;
      // Normalize index to prevent overflow
      const normalizedIndex = index - levelMin;
      if (node.left) queue.push([node.left, 2 * normalizedIndex]);
      if (node.right) queue.push([node.right, 2 * normalizedIndex + 1]);
    }
  }
  return maxWidth;
}

// Driver code
const root = new TreeNode(1,
  new TreeNode(2, new TreeNode(4), null),
  new TreeNode(3, null, new TreeNode(5))
);
console.log(widthOfBinaryTree(root));

const queue: Array<[TreeNode, number]> = [[root, 0]];

Initialize queue with root node and index 0 to track positions

const levelIndices = queue.map(pair => pair[1]);

Collect indices of nodes at current level to calculate width

const levelMin = levelIndices[0]; const levelMax = levelIndices[levelIndices.length - 1];

Find leftmost and rightmost indices to measure width

maxWidth = Math.max(maxWidth, levelMax - levelMin + 1);

Update maximum width if current level is wider

const [node, index] = queue.shift()!; const normalizedIndex = index - levelMin;

Remove node from queue and normalize index to avoid large numbers

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

Add children to queue with calculated indices to keep track of positions

Output

4

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 level counting without indices, this method counts gaps correctly and avoids missing width caused by null nodes

Edge Cases

Empty tree

Returns 0 as there are no nodes

DSA Typescript

if (!root) return 0;

Tree with only root node

Returns 1 as width is just the root

DSA Typescript

maxWidth = Math.max(maxWidth, levelMax - levelMin + 1);

Tree with missing children causing gaps

Correctly counts width including null gaps using indices

DSA Typescript

const normalizedIndex = index - levelMin;

When to Use This Pattern

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

Common Mistakes

Mistake: Counting only existing nodes at each level without considering gaps
Fix: Use indices to track positions and calculate width as rightmost index minus leftmost index plus one

Summary

Finds the maximum width of a binary tree including gaps between nodes.

Use when you need to measure the widest level in a tree counting empty spots.

Assign indices to nodes during level order traversal to track positions and calculate width accurately.