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
           / \
         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 */
    /* 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(nonFullNode == true)
                return false;
  } else {
      nonFullNode = true;
      if(nonFullNode == true)
   return false;
  } else {
      nonFullNode = true;
    return true;

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