# AC JAVA Solution with Explanation

• A property of Binary tree is that index of left child = index of parent2, index of right child = index of parent2 + 1.We could use this to get the width for each level.

public int widthOfBinaryTree(TreeNode root) {
if(root==null) return 0;
if(root.left==null&&root.right==null) return 1;
LinkedList<Integer> q2 = new LinkedList<>(); // queue that keep track of index of each node
q1.offer(root);
q2.offer(1);
int size = 1;// keep track of current num of nodes in q1 for each level
int max = Integer.MIN_VALUE;
boolean fir = false;// judge whether its the first node in a new level
int start = Integer.MAX_VALUE;// record index of first node in a new level
while(!q1.isEmpty()){
TreeNode node = q1.poll();
int i = q2.poll();
size--;
if(fir){
start = i;
fir = false;
}
if(node.left!=null){
q1.offer(node.left);
q2.offer(i*2);
}
if(node.right!=null){
q1.offer(node.right);
q2.offer(i*2+1);
}
if(size==0){
fir = true;
size = q1.size();
max = Math.max(max, i - start + 1);// the i is the index of last node in this level
}
}
return max;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.