Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Maximum Width of Binary Tree

LeetCode #662Medium
Index nodes by position 2i, 2i+1

Given the root of a binary tree, return the maximum width across all levels, where a level's width is the distance between its leftmost and rightmost non-null nodes counting the null positions between them as if the tree were a complete binary tree.

Asked atAmazonMicrosoft
step 1 / 15
binary tree
5
3
3
1
2
9
queue (node, index)
front →
(empty)
← back
BFS with position indices
▸
1widthOfTree(root):
2    queue = [(root, 0)]
3    while queue not empty:
4        base = queue.front.index   // normalize
5        width = queue.back.index - base + 1
6        maxWidth = max(maxWidth, width)
7        for _ in range(len(queue)):
8            node, i = queue.dequeue()   // i already normalized
9            enqueue (node.left, 2*i), (node.right, 2*i+1)
10    return maxWidth
state
  • ruleleft=2i right=2i+1
  • maxWidth0

line 1LeetCode 662 — maximum width of a level, counting the NULL gaps in between. We give every node a position index as if the tree were a perfect array: root = 0, a left child of i is 2i, a right child is 2i+1. The width of a level is (rightmost index − leftmost index + 1).