Maximum Width of Binary Tree Visualizer & Step-by-Step Algorithm Solution

Calculate the maximum width among all levels of a binary tree by assigning 0-indexed position coordinates and normalizing each level against its starting index.

Category: trees | Difficulty: Medium

Tags: BFS, Binary Tree, Queue, Tree Width, Level Order Traversal

Maximum Width of Binary Tree

1
3
5
3
2
9
BFS QUEUE
(Queue Empty)
100%
state
totalNodes6
Initialization
1/51
Explanation

Starting widthOfBinaryTree with root Node(1).

Source Code
1function widthOfBinaryTree(root: TreeNode | null): number {
2 if (!root) return 0;
3 let queue: [TreeNode, number][] = [[root, 0]];
4 let maxWidth: number = 0;
5 while (queue.length) {
6 let levelSize = queue.length;
7 const startIndex = queue[0][1];
8 let first = 0;
9 let last = 0;
10 for (let i = 0; i < levelSize; i++) {
11 const [node, index] = queue.shift()!;
12 const normalizedIndex = index - startIndex;
13
14 if (i === 0) first = normalizedIndex;
15 if (i === levelSize - 1) last = normalizedIndex;
16
17 if (node.left) queue.push([node.left, 2 * normalizedIndex + 1]);
18 if (node.right) queue.push([node.right, 2 * normalizedIndex + 2]);
19 }
20 maxWidth = Math.max(maxWidth, last - first + 1);
21 }
22 return maxWidth;
23}