Maximum Width of Binary Tree Medium 0 attempts
LeetCode ↗

Maximum Width of Binary Tree

Medium TreeBinary TreeDFS LeetCode

Given the root of a binary tree, return the maximum width of the given tree. The maximum width is the maximum length between the leftmost and rightmost non-null nodes at any level, where null nodes between them are also counted.

Example:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Sample Input
—
Sample Output
—
Constraints
  • 1 <= number of nodes <= 3000
  • -100 <= Node.val <= 100
Test Cases
Case 1
Args: [[1,3,2,5,3,null,9]] Expected: 4
Case 2
Args: [[1]] Expected: 1
Topics
TreeBinary TreeDFS

Approach: BFS with Position Indexing

Assign a position index to each node: root is 0, left child is 2pos, right is 2pos+1. Width at each level is rightmost - leftmost + 1. Use BigInt to avoid overflow for deep trees.

function maximumWidthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  const queue = [[root, 0n]];
  while (queue.length) {
    const size = queue.length;
    const first = queue[0][1];
    let last = first;
    for (let i = 0; i < size; i++) {
      const [node, pos] = queue.shift();
      last = pos;
      if (node.left) queue.push([node.left, 2n * pos]);
      if (node.right) queue.push([node.right, 2n * pos + 1n]);
    }
    maxWidth = Math.max(maxWidth, Number(last - first + 1n));
  }
  return maxWidth;
}

Time Complexity: O(n)

Space Complexity: O(n)

Saved in this browser only. Private to you.

JavaScript