Check whether a given binary tree is perfect or not | C ++ program to check whether a given Binary Tree is Perfect or not ; Tree node structure ; Returns depth of leftmost leaf . ; This function tests if a binary tree is perfect or not . It basically checks for two things : 1 ) All leaves are at same level 2 ) All internal nodes have two children ; An empty tree is perfect ; If leaf node , then its depth must be same as depth of all other leaves . ; If internal node and one child is empty ; Left and right subtrees must be perfect . ; Wrapper over isPerfectRec ( ) ; Helper function that allocates a new node with the given key and NULL left and right pointer . ; Driver Program
#include <bits/stdc++.h> NEW_LINE struct Node { int key ; struct Node * left , * right ; } ; int findADepth ( Node * node ) { int d = 0 ; while ( node != NULL ) { d ++ ; node = node -> left ; } return d ; } bool isPerfectRec ( struct Node * root , int d , int level = 0 ) { if ( root == NULL ) return true ; if ( root -> left == NULL && root -> right == NULL ) return ( d == level + 1 ) ; if ( root -> left == NULL root -> right == NULL ) return false ; return isPerfectRec ( root -> left , d , level + 1 ) && isPerfectRec ( root -> right , d , level + 1 ) ; } bool isPerfect ( Node * root ) { int d = findADepth ( root ) ; return isPerfectRec ( root , d ) ; } struct Node * newNode ( int k ) { struct Node * node = new Node ; node -> key = k ; node -> right = node -> left = NULL ; return node ; } int main ( ) { struct Node * root = NULL ; root = newNode ( 10 ) ; root -> left = newNode ( 20 ) ; root -> right = newNode ( 30 ) ; root -> left -> left = newNode ( 40 ) ; root -> left -> right = newNode ( 50 ) ; root -> right -> left = newNode ( 60 ) ; root -> right -> right = newNode ( 70 ) ; if ( isPerfect ( root ) ) printf ( " Yes STRNEWLINE " ) ; else printf ( " No STRNEWLINE " ) ; return ( 0 ) ; }