Check if removing an edge can divide a Binary Tree in two halves | C ++ program to check if there exist an edge whose removal creates two trees of same size ; utility function to create a new node ; To calculate size of tree with given root ; This function returns size of tree rooted with given root . It also set " res " as true if there is an edge whose removal divides tree in two halves . n is size of tree ; Base case ; Compute sizes of left and right children ; If required property is true for current node set " res " as true ; Return size ; This function mainly uses checkRec ( ) ; Count total nodes in given tree ; Initialize result and recursively check all nodes ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newNode ( int x ) { struct Node * temp = new Node ; temp -> data = x ; temp -> left = temp -> right = NULL ; return temp ; } ; int count ( Node * root ) { if ( root == NULL ) return 0 ; return count ( root -> left ) + count ( root -> right ) + 1 ; } int checkRec ( Node * root , int n , bool & res ) { if ( root == NULL ) return 0 ; int c = checkRec ( root -> left , n , res ) + 1 + checkRec ( root -> right , n , res ) ; if ( c == n - c ) res = true ; return c ; } bool check ( Node * root ) { int n = count ( root ) ; bool res = false ; checkRec ( root , n , res ) ; return res ; } int main ( ) { struct Node * root = newNode ( 5 ) ; root -> left = newNode ( 1 ) ; root -> right = newNode ( 6 ) ; root -> left -> left = newNode ( 3 ) ; root -> right -> left = newNode ( 7 ) ; root -> right -> right = newNode ( 4 ) ; check ( root ) ? printf ( " YES " ) : printf ( " NO " ) ; return 0 ; }