Check if removing an edge can divide a Binary Tree in two halves | Java program to check if there exist an edge whose removal creates two trees of same size ; 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
class Node { int key ; Node left , right ; public Node ( int key ) { this . key = key ; left = right = null ; } } class Res { boolean res = false ; } class BinaryTree { Node root ; int count ( Node node ) { if ( node == null ) return 0 ; return count ( node . left ) + count ( node . right ) + 1 ; } int checkRec ( Node root , int n , Res res ) { if ( root == null ) return 0 ; int c = checkRec ( root . left , n , res ) + 1 + checkRec ( root . right , n , res ) ; if ( c == n - c ) res . res = true ; return c ; } boolean check ( Node root ) { int n = count ( root ) ; Res res = new Res ( ) ; checkRec ( root , n , res ) ; return res . res ; } public static void main ( String [ ] args ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 5 ) ; tree . root . left = new Node ( 1 ) ; tree . root . right = new Node ( 6 ) ; tree . root . left . left = new Node ( 3 ) ; tree . root . right . left = new Node ( 7 ) ; tree . root . right . right = new Node ( 4 ) ; if ( tree . check ( tree . root ) == true ) System . out . println ( " YES " ) ; else System . out . println ( " NO " ) ; } }