Program to Check Whether a Binary Tree is Complete Tree or Not

• Write a C++ program to check whether a binary tree is complete tree.

Given a binary tree, we have to check whether given binary tree is complete tree or not.
In a Complete binary tree all levels of a binary tree is completely filled only the last level of tree can be partially filled. All the nodes in last level must be filled from left to right.

---

Method 1

Algorithm to check whether a binary tree is complete tree

• A Complete binary tree contain three type of nodes.
  1. Full Node : A node having left and right child both.
  2. Partial Node : A node having only left child. A node having only right child is not possible in complete tree. If we found a only right child node then it is not a complete tree.
  3. Leaf Node : A node whose both children's are NULL.
• A complete binary tree may contain only one partial node. More than one partial node means not a complete tree.
• Perform level order traversal using a Queue. Whenever we remove a node from Queue, check if it is a partial node.
• Once we found a partial node, all the nodes after this node must be a leaf node.
• If we don't find any partial node in whole tree, then given binary tree is full tree and hence a complete tree also.

Time Complexity : O(n)
Space Complexity : O(n), required for queue in level order traversal.

---

C++ program to check for complete binary tree.

#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \  / \
       4  5 6  7
      / \
     8  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
 
    root->left->left->left = getNewNode(8);
    root->left->left->right = getNewNode(9);
    
    return root;
}

/* This function checks whether binary tree is full or not. 
Does level order traversal using a queue. It checks that after 
a Non Full node, all nodes must be leaf node otherwise not a 
full binary tree. 

NOTE : Non full Nodes are either leaf nodes or 
nodes having only one child node */
bool isFullBinaryTree(struct node *root) {
    /* Empty Tree */
    if(root == NULL)  
     return true;
 
    /* Create a Queue for doing level order traversal */
    queue<node*> Q;
    /* We will mark this flag as true after 
 seeing first non full node */
    int nonFullNode = false;
 
    /* Push root node inside queue */
    Q.push(root);
 
    /* Traverse level order and check IF current node 
 is Non Full node. After first non full node all 
 node must be leaf node */
    while(!Q.empty()) {
        struct node *node = Q.front();
            
        if(node->left){
            if(nonFullNode == true)
                return false;
             
            Q.push(node->left);
  } else {
      nonFullNode = true;
  }
   
  if(node->right){
      if(nonFullNode == true)
   return false;
    
      Q.push(node->right);
  } else {
      nonFullNode = true;
  }
        Q.pop();
    }
        
    return true;
}

int main() {
    struct node *root = generateBTree();    
    
    /* Check IF binary tree is 
 full binary tree or not  */
    if(isFullBinaryTree(root)){
     printf("Full Binary Tree\n");
 } else {
  printf("Non Full Binary Tree\n");
 }
    
 /*Modifying tree to make is non ful tree */
    root->right->right = NULL;
    
    if(isFullBinaryTree(root)){
     printf("Full Binary Tree\n");
 } else {
  printf("Non Full Binary Tree\n");
 }
 
    getchar();
    return 0; 
}

Output

Full Binary Tree
Non Full Binary Tree