//C++ program to check whether a given binary tree is perfect or not
#include<iostream>
using namespace std; 
  
template <typename T>		//creating a new node
struct Node
{
   T data=0;
   Node<T>* left=nullptr;
   Node<T>* right=nullptr;
   
};

template <typename T>		//function template to create binary tree
Node<T>* createTree()
{
   //creating all nodes needed in the binary tree
   Node<T>* node1 = new Node<T>; 
   node1->data = 1;
   Node<T>* node2 = new Node<T>; 
   node2->data = 2;
   Node<T>* node3 = new Node<T>; 
   node3->data = 3;
   Node<T>* node4 = new Node<T>;
   node4->data = 4;
   Node<T>* node5 = new Node<T>; 
   node5->data = 5;
   Node<T>* node6 = new Node<T>; 
   node6->data = 6;
   Node<T>* node7 = new Node<T>; 
   node7->data = 7;
   Node<T>* node8 = new Node<T>; 
   node8->data = 8;
   Node<T>* node9 = new Node<T>; 
   node9->data = 9;
   Node<T>* node10 = new Node<T>; 
   node10->data = 10;
   
   //connecting nodes to create a binary tree
   node1->left = node2;
   node1->right = node3;
   node2->right = node4;
   node4->left = node5; 
   node4->right = node6;
   node3->left = node7;
   node7->right = node8;
   node8->left = node9;
   node8->right = node10;
   

   return node1;	//returning the root node as it is connected to every node
}


template<typename T>
int depth(Node<T> *node) 
{ 
   int i = 0; 
   while (node != NULL) 
   { 
      i++; 
      node = node->left; 
   } 
   return i; 
} 
  
//template to test if binary tree is perfect or not
template<typename T>
bool checktree(Node<T>* root, int d, int level = 0) 
{ 
    if (root == NULL) 
        return true; 
  
    // If this is a depth of leaf node then all other leaf nodes should have same depth
    if (root->left == NULL && root->right == NULL) 
        return (d == level+1); 
  
    // If internal node and one child is empty 
    if (root->left == NULL || root->right == NULL) 
        return false; 
  
    // Left and right subtrees should be perfect. 
    return checktree(root->left, d, level+1) && checktree(root->right, d, level+1); 
} 

//calling depth and checktree function to check if tree is perfect or not 
template <typename T> 
bool isPerfect(Node<T> *root) 
{ 
   int d = depth(root); 
   return checktree(root, d); 
} 
  
int main() 
{ 
    Node<int>* root = createTree<int>();  //creating tree
  
    if (isPerfect(root)) 
        printf("Yes it's a perfect binary tree\n"); 
    else
        printf("No it's not a perfect binary tree\n"); 
  
    return(0); 
} 

OUTPUT: