Maximum Width of Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation for a Simple Tree

What is the output of the following TypeScript code that calculates the maximum width of a binary tree?

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;
  let queue: Array<[TreeNode, number]> = [[root, 0]];
  while (queue.length > 0) {
    const levelLength = queue.length;
    const levelHeadIndex = queue[0][1];
    let lastIndex = 0;
    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift()!;
      lastIndex = index;
      if (node.left) queue.push([node.left, 2 * (index - levelHeadIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - levelHeadIndex) + 1]);
    }
    maxWidth = Math.max(maxWidth, lastIndex - levelHeadIndex + 1);
  }
  return maxWidth;
}

const root = new TreeNode(1,
  new TreeNode(3,
    new TreeNode(5),
    new TreeNode(3)
  ),
  new TreeNode(2,
    null,
    new TreeNode(9)
  )
);

console.log(widthOfBinaryTree(root));

A 4

B 3

C 5

D 2

💡 Hint

Consider the width as the number of nodes between the leftmost and rightmost nodes at each level, counting nulls in between.

The maximum width is 4 at the third level: nodes 5, 3, null, 9. The code uses indexing to count positions including gaps.

🧠 Conceptual

intermediate

Understanding the Role of Indexing in Width Calculation

Why does the algorithm assign indices to nodes when calculating the maximum width of a binary tree?

A To track the horizontal position of nodes including gaps caused by missing children

B To count the total number of nodes in the tree

C To determine the depth of the tree

D To sort nodes by their values

💡 Hint

Think about how to measure width including empty spaces between nodes.

Indices represent positions as if the tree was a complete binary tree, allowing calculation of width including null gaps.

🔧 Debug

advanced

Identify the Error in Width Calculation Code

What error will the following TypeScript code produce when calculating the maximum width of a binary tree?

DSA Typescript

function widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let maxWidth = 0;
  let queue: Array<[TreeNode, number]> = [[root, 0]];
  while (queue.length > 0) {
    const levelLength = queue.length;
    const levelHeadIndex = queue[0][1];
    let lastIndex = 0;
    for (let i = 0; i <= levelLength; i++) {
      const [node, index] = queue.shift()!;
      lastIndex = index;
      if (node.left) queue.push([node.left, 2 * (index - levelHeadIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - levelHeadIndex) + 1]);
    }
    maxWidth = Math.max(maxWidth, lastIndex - levelHeadIndex + 1);
  }
  return maxWidth;
}

A No error, code runs correctly

B Runtime error due to queue.shift() returning undefined

C Syntax error because of missing semicolon

D Incorrect maximum width due to off-by-one in loop condition

💡 Hint

Check the loop condition and how many times queue.shift() is called.

The for loop uses i <= levelLength, causing one extra iteration. queue.shift() returns undefined on last iteration, causing runtime error.

❓ Predict Output

advanced

Maximum Width for a Skewed Binary Tree

What is the output of the following TypeScript code that calculates the maximum width of a skewed binary tree?

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;
  let queue: Array<[TreeNode, number]> = [[root, 0]];
  while (queue.length > 0) {
    const levelLength = queue.length;
    const levelHeadIndex = queue[0][1];
    let lastIndex = 0;
    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift()!;
      lastIndex = index;
      if (node.left) queue.push([node.left, 2 * (index - levelHeadIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - levelHeadIndex) + 1]);
    }
    maxWidth = Math.max(maxWidth, lastIndex - levelHeadIndex + 1);
  }
  return maxWidth;
}

const root = new TreeNode(1,
  new TreeNode(2,
    new TreeNode(3,
      new TreeNode(4),
      null
    ),
    null
  ),
  null
);

console.log(widthOfBinaryTree(root));

A 4

B 2

C 3

D 1

💡 Hint

A skewed tree has only one node per level, so width is always 1.

Each level has only one node, so maximum width is 1.

🧠 Conceptual

expert

Why Normalize Indices at Each Level in Width Calculation?

In the maximum width calculation algorithm, why do we subtract the index of the first node at the current level from all node indices before calculating children indices?

A To count the total number of nodes in the tree

B To sort nodes by their values at each level

C To prevent integer overflow and keep indices small for large trees

D To reverse the order of nodes at each level

💡 Hint

Think about how indices grow as the tree depth increases.

Without normalization, indices double each level and can become very large, causing overflow or performance issues.

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, not height or sum [OK]

Common Mistakes:

• Confusing width with height of the tree
• Thinking width is total nodes in the tree
• Assuming width is sum of node values

2. Which TypeScript data structure is best suited to track nodes level by level when finding maximum width of a binary tree?

easy

A. Queue

B. Stack

C. Set

D. Map

Solution

1. Step 1: Identify traversal method for levels

   Level order traversal visits nodes level by level, which uses a queue.

2. Step 2: Choose data structure for level order

   A queue allows FIFO order, perfect for processing nodes in each level sequentially.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level-by-level traversal [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Using set which doesn't maintain order
• Using map which is key-value, not for traversal order

3. What will be the output of the following TypeScript code snippet that calculates maximum width of a binary tree?

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

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

function maxWidth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue: Array<TreeNode> = [root];
  let maxWidth = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    maxWidth = Math.max(maxWidth, levelSize);
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

console.log(maxWidth(root));

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Analyze tree structure and levels

   Level 1: Node 1 (width 1) Level 2: Nodes 2, 3 (width 2) Level 3: Nodes 4, 5 (width 2)

2. Step 2: Check code logic for max width

   Code tracks queue length per level and updates maxWidth. Max width found is 2 at levels 2 and 3.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at widest level [OK]

Hint: Count nodes per level, track max count [OK]

Common Mistakes:

• Counting total nodes instead of per level
• Assuming width is height of tree
• Ignoring null children in width calculation

4. The following TypeScript function aims to find the maximum width of a binary tree but has a bug. What is the bug?

function maxWidth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue: Array<TreeNode> = [root];
  let maxWidth = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    maxWidth = Math.max(maxWidth, levelSize);
    for (let i = 0; i <= levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

medium

A. The maxWidth should be updated after the for loop

B. The queue should be a stack for correct traversal

C. The for loop condition should be i < levelSize, not i <= levelSize

D. The function should return queue.length instead of maxWidth

Solution

1. Step 1: Examine the for loop condition

   The loop runs from i = 0 to i <= levelSize, which means it runs levelSize + 1 times.

2. Step 2: Identify impact of off-by-one error

   Calling queue.shift() one extra time causes undefined or error because queue is empty after levelSize removals.

3. Final Answer:

   The for loop condition should be i < levelSize, not i <= levelSize -> Option C

4. Quick Check:

   Loop runs exactly levelSize times [OK]

Hint: Use i < levelSize for loops over fixed-size levels [OK]

Common Mistakes:

• Using <= instead of < in loops causing extra iteration
• Confusing queue with stack for level order
• Updating maxWidth inside loop incorrectly

5. Given a binary tree where some nodes are missing (null), how can you modify the maximum width calculation to include the '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 to solve this problem in TypeScript.

hard

A. Count only non-null nodes per level ignoring positions

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

C. Use a stack instead of a queue to track nodes

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

Solution

1. Step 1: Understand the problem with missing nodes

   Simply counting nodes misses gaps caused by nulls, so width must consider positions.

2. Step 2: Use indexing like a complete binary tree

   Assign indices to nodes: root = 0, left child = 2*index, right child = 2*index + 1. Track min and max indices per level to find width including gaps.

3. Final Answer:

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

4. Quick Check:

   Index nodes to include null gaps [OK]

Hint: Use complete tree indexing to count gaps [OK]

Common Mistakes:

• Ignoring null gaps and counting only nodes
• Using stack which breaks level order
• Summing node values instead of counting width