Check whether a given Binary Tree is Complete or not

Given a Binary Tree, write a function to check whether the given Binary Tree is Complete Binary Tree or not.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. See following examples.

The following trees are examples of Complete Binary Trees
    1
  /   \
 2     3
  
       1
    /    \
   2       3
  /
 4

       1
    /    \
   2      3
  /  \    /
 4    5  6

The following trees are examples of Non-Complete Binary Trees
    1
      \
       3
  
       1
    /    \
   2       3
    \     /  \   
     4   5    6

       1
    /    \
   2      3
         /  \
        4    5

The method 2 of level order traversal post can be easily modified to check whether a tree is Complete or not. To understand the approach, let us first define a term ‘Full Node’. A node is ‘Full Node’ if both left and right children are not empty (or not NULL).

The approach is to do a level order traversal starting from root. In the traversal, once a node is found which is NOT a Full Node, all the following nodes must be leaf nodes.
Also, one more thing needs to be checked to handle the below case: If a node has empty left child, then the right child must be empty.

    1
  /   \
 2     3
  \
   4

// A program to check if a given binary tree is complete or not #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAX_Q_SIZE 500   /* A binary tree node has data, pointer to left child    and a pointer to right child */ struct node {     int data;     struct node* left;     struct node* right; };   /* frunction prototypes for functions needed for Queue data    structure. A queue is needed for level order tarversal */ struct node** createQueue(int *, int *); void enQueue(struct node **, int *, struct node *); struct node *deQueue(struct node **, int *); bool isQueueEmpty(int *front, int *rear);   /* Given a binary tree, return true if the tree is complete    else false */ bool isCompleteBT(struct node* root) {   // Base Case: An empty tree is complete Binary Tree   if (root == NULL)     return true;     // Create an empty queue   int rear, front;   struct node **queue = createQueue(&front, &rear);     // Create a flag variable which will be set true   // when a non full node is seen   bool flag = false;     // Do level order traversal using queue.   enQueue(queue, &rear, root);   while(!isQueueEmpty(&front, &rear))   {     struct node *temp_node = deQueue(queue, &front);       /* Ceck if left child is present*/     if(temp_node->left)     {        // If we have seen a non full node, and we see a node        // with non-empty left child, then the given tree is not        // a complete Binary Tree        if (flag == true)          return false;          enQueue(queue, &rear, temp_node->left);  // Enqueue Left Child     }     else // If this a non-full node, set the flag as true        flag = true;       /* Ceck if right child is present*/     if(temp_node->right)     {        // If we have seen a non full node, and we see a node        // with non-empty left child, then the given tree is not        // a complete Binary Tree        if(flag == true)          return false;          enQueue(queue, &rear, temp_node->right);  // Enqueue Right Child     }     else // If this a non-full node, set the flag as true        flag = true;   }     // If we reach here, then the tree is complete Bianry Tree   return true; }     /*UTILITY FUNCTIONS*/ struct node** createQueue(int *front, int *rear) {   struct node **queue =    (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);     *front = *rear = 0;   return queue; }   void enQueue(struct node **queue, int *rear, struct node *new_node) {   queue[*rear] = new_node;   (*rear)++; }   struct node *deQueue(struct node **queue, int *front) {   (*front)++;   return queue[*front - 1]; }   bool isQueueEmpty(int *front, int *rear) {    return (*rear == *front); }   /* Helper function that allocates a new node with the    given data and NULL left and right pointers. */ struct node* newNode(int data) {   struct node* node = (struct node*)                        malloc(sizeof(struct node));   node->data = data;   node->left = NULL;   node->right = NULL;     return(node); }   /* Driver program to test above functions*/ int main() {    /* Let us construct the following Binary Tree which       is not a complete Binary Tree             1           /   \          2     3         / \     \        4   5     6     */     struct node *root  = newNode(1);   root->left         = newNode(2);   root->right        = newNode(3);   root->left->left   = newNode(4);   root->left->right  = newNode(5);   root->right->right = newNode(6);     if ( isCompleteBT(root) == true )       printf ("Complete Binary Tree");   else       printf ("NOT Complete Binary Tree");     return 0; }