Find the maximum width of a binary tree?

int WidthOfBinaryTree(TreeNode root) {

if (root == null) return 0;

int maxWidth = 0;

Queue<(TreeNode node, int idx)> queue = new Queue<(TreeNode,

int)>();

queue.Enqueue((root, 0));

while (queue.Count > 0) {

int size = queue.Count;

int start = queue.Peek().idx;

int end = start;

for (int i = 0; i < size; i++) {

var (node, idx) = queue.Dequeue();

end = idx;

if (node.left != null)

queue.Enqueue((node.left, 2 * idx + 1));

if (node.right != null)

queue.Enqueue((node.right, 2 * idx + 2));

maxWidth = Math.Max(maxWidth, end - start + 1);

Follow on:

return maxWidth;

Explanation:

Assign index to each node as if in a complete tree; width is max difference of indices per

level.