# 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
```