Complete Binary Tree: Has a Simple solution but yet a little difficult to think about it.

In this problem we are given a binary tree and we need to find whether if it is a complete binary tree or not. Before we discuss on the solution lets say on the possible discussions. If we know that when we traverse in Breadth fashion way and if we encounter a null value that has to be last element in the tree. So for this you try to add a element in the Que such that it indicates that the level has completed. so you pop the elements and each popped element should not have any children. Well this approach will not cover some corner cases.

Now lets discuss on the solution, Since you are traversing in the BFS fashion, Let us define a flag variable which is set to true when ever the child is found to be a null. Let the removed node from the Que be X. While looking for its left or right child and if you find flag is true and you find a child then you can return false isn't it? As you already have come across a null value and you are not supposed to see a non value from that point. Here is the solution.

class GfG
{
	boolean isCompleteBT(Node root)
    {
          //add code here.
          Queue<Node> q = new LinkedList<>();
          if(root==null) return true;
          q.add(root);
          boolean flag = false;
          while(!q.isEmpty()){
              Node temp = q.remove();
              if(temp.left!=null){
                  if(flag==true) return false;
                  q.add(temp.left);
              }
              else flag = true;
              if(temp.right!=null){
                  if(flag==true) return false;
                  q.add(temp.right);
              }
              else flag = true;
              
          }
          
         return true;
	} 
}