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.