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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation

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

DSA Javascript

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

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  let queue = [[root, 0]]; // node and index

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

    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift();
      if (node.left) queue.push([node.left, 2 * (index - minIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - minIndex) + 1]);
    }
  }
  return maxWidth;
}

// Tree structure:
//       1
//      / \
//     3   2
//    /     \
//   5       9
//  /         \
// 6           7

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

console.log(widthOfBinaryTree(root));

A 4

B 8

C 5

D 6

💡 Hint

Consider how the indices are assigned to nodes and how the width is calculated as the difference between max and min indices at each level.

The maximum width is calculated by tracking the indices of nodes at each level. The widest level here includes nodes at indices 0 to 7 (after normalization), so the width is 8.

❓ Predict Output

intermediate

Maximum Width for a Skewed Tree

What is the output of the code below for a skewed binary tree (all nodes only have a right child)?

DSA Javascript

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

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  let queue = [[root, 0]];

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

    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift();
      if (node.left) queue.push([node.left, 2 * (index - minIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - minIndex) + 1]);
    }
  }
  return maxWidth;
}

// Tree structure:
// 1 -> 2 -> 3 -> 4 (all right children)
const root = new TreeNode(1,
  null,
  new TreeNode(2,
    null,
    new TreeNode(3,
      null,
      new TreeNode(4)
    )
  )
);

console.log(widthOfBinaryTree(root));

A 3

B 2

C 4

D 1

💡 Hint

In a skewed tree, the width at each level is usually 1 because there is only one node per level.

Since each level has only one node, the width at every level is 1, so the maximum width is 1.

🔧 Debug

advanced

Identify the Error in Width Calculation

The following code attempts to calculate the maximum width of a binary tree but produces incorrect results. What is the main reason for the error?

DSA Javascript

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  let queue = [[root, 0]];

  while (queue.length > 0) {
    const levelLength = queue.length;
    const minIndex = queue[0][1];
    const maxIndex = queue[levelLength - 1][1];
    maxWidth = Math.max(maxWidth, maxIndex - minIndex + 1);

    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift();
      if (node.left) queue.push([node.left, 2 * index]);
      if (node.right) queue.push([node.right, 2 * index + 1]);
    }
  }
  return maxWidth;
}

A The maxWidth calculation should use multiplication instead of subtraction.

B The queue is not initialized properly with root and index 1 instead of 0.

C Indices are not normalized by subtracting minIndex, causing overflow and incorrect width.

D The function does not handle null nodes in the queue, causing runtime errors.

💡 Hint

Check how indices are assigned to child nodes relative to the current level's minimum index.

Without normalizing indices by subtracting minIndex, indices can grow very large, causing incorrect width calculations due to integer overflow or gaps.

🧠 Conceptual

advanced

Why Use Index Normalization in Maximum Width Calculation?

Why is it important to normalize indices by subtracting the minimum index at each level when calculating the maximum width of a binary tree?

A To prevent integer overflow and keep indices small for accurate width calculation.

B To ensure the tree is balanced before calculating width.

C To sort the nodes at each level by their values.

D To convert the tree into a linked list for easier traversal.

💡 Hint

Think about what happens to indices as the tree depth increases.

Indices can become very large in deep trees, causing overflow or incorrect width calculations. Normalizing keeps indices relative and small.

🚀 Application

expert

Maximum Width of Binary Tree with Missing Nodes

Given the following binary tree, what is the maximum width calculated by the standard algorithm that uses index normalization? // Tree structure: // 1 // / \ // 2 3 // \ \ // 5 7 // / \ // 9 8

DSA Javascript

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

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  let queue = [[root, 0]];

  while (queue.length > 0) {
    const levelLength = queue.length;
    const minIndex = queue[0][1];
    const maxIndex = queue[levelLength - 1][1];
    maxWidth = Math.max(maxWidth, maxIndex - minIndex + 1);

    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift();
      if (node.left) queue.push([node.left, 2 * (index - minIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - minIndex) + 1]);
    }
  }
  return maxWidth;
}

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

console.log(widthOfBinaryTree(root));

A 6

B 5

C 8

D 7

💡 Hint

Consider the indices assigned to nodes at the third level and how gaps affect width.

At the third level, nodes 9 and 8 are at indices 0 and 5 respectively after normalization, so width is 6 (5 - 0 + 1). This is the maximum width.