662. Maximum Width of Binary Tree

import javafx.util.Pair;

import java.util.ArrayDeque;

import java.util.Deque;

// Definition for a binary tree node.

public class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode() {}

    TreeNode(int val) { this.val = val; }

    TreeNode(int val, TreeNode left, TreeNode right) {

        this.val = val;

        this.left = left;

        this.right = right;

    }

}

class Solution {

    public int widthOfBinaryTree(TreeNode root) {

        if(root == null) return 0;

        int ans = 0;

        Deque<Pair<TreeNode, Integer>> deque = new ArrayDeque<>();

        deque.add(new Pair<>(root, 0));

        while(!deque.isEmpty()){

            int len = deque.size();

            int start = deque.peekFirst().getValue();

            int end = deque.peekLast().getValue();

            ans = Math.max(ans, end - start + 1);

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

                Pair<TreeNode, Integer> node = deque.pop();

                TreeNode curr = node.getKey();

                int index = node.getValue();

                if(curr.left != null) 

                    deque.add(new Pair<>(curr.left, 2 * index));

                if(curr.right != null)

                    deque.add(new Pair<>(curr.right, 2 * index + 1));

            }

        }

        return ans;

    }

}