- 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.
__Full Node__: A node having left and right child both.__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.__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