Maximum Width of Binary Tree Medium 0 attempts
LeetCode ↗

Maximum Width of Binary Tree

Medium TreeBinary TreeDFS LeetCode

You're given the root of a binary tree. Return its maximum width, measured as the greatest distance between the leftmost and rightmost non-null nodes on any single level — counting the null gaps that fall between them as if they were present.

Input Format
Implement maximumWidthOfBinaryTree(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
root = [1,3,2,5,3,null,9]
Output
4

Example 2

Input
root = [1]
Output
1
Constraints
  • 1 <= number of nodes <= 3000
  • -100 <= Node.val <= 100
  • The maximum width fits in a signed 32-bit integer.
Test Cases (2)
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.

javascript
function maximumWidthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  const queue = [[root, 0n]];
  let head = 0;
  while (head < queue.length) {
    const size = queue.length - head;
    const first = queue[0][1];
    let last = first;
    for (let i = 0; i < size; i++) {
      const [node, pos] = queue[head++];
      last = pos;
      const offset = pos - first;
      if (node.left) queue.push([node.left, 2n * offset]);
      if (node.right) queue.push([node.right, 2n * offset + 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