Check if all leaves are at same level | C ++ program to check if all leaves are at same level ; A binary tree node ; A utility function to allocate a new tree node ; Recursive function which checks whether all leaves are at same level ; Base case ; If a leaf node is encountered ; When a leaf node is found first time ; Set first found leaf 's level ; If this is not first leaf node , compare its level with first leaf 's level ; If this node is not leaf , recursively check left and right subtrees ; The main function to check if all leafs are at same level . It mainly uses checkUtil ( ) ; Driver Code ; Let us create tree shown in third example
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int data ) { struct Node * node = ( struct Node * ) malloc ( sizeof ( struct Node ) ) ; node -> data = data ; node -> left = node -> right = NULL ; return node ; } bool checkUtil ( struct Node * root , int level , int * leafLevel ) { if ( root == NULL ) return true ; if ( root -> left == NULL && root -> right == NULL ) { if ( * leafLevel == 0 ) { * leafLevel = level ; return true ; } return ( level == * leafLevel ) ; } return checkUtil ( root -> left , level + 1 , leafLevel ) && checkUtil ( root -> right , level + 1 , leafLevel ) ; } bool check ( struct Node * root ) { int level = 0 , leafLevel = 0 ; return checkUtil ( root , level , & leafLevel ) ; } int main ( ) { struct Node * root = newNode ( 12 ) ; root -> left = newNode ( 5 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 9 ) ; root -> left -> left -> left = newNode ( 1 ) ; root -> left -> right -> left = newNode ( 1 ) ; if ( check ( root ) ) cout << " Leaves ▁ are ▁ at ▁ same ▁ level STRNEWLINE " ; else cout << " Leaves ▁ are ▁ not ▁ at ▁ same ▁ level STRNEWLINE " ; getchar ( ) ; return 0 ; }