Check if removing an edge can divide a Binary Tree in two halves | javascript 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 { constructor ( key ) { this . key = key ; this . left = this . right = null ; } } class Res { constructor ( ) { this . res = false ; } } var root ; function count ( node ) { if ( node == null ) return 0 ; return count ( node . left ) + count ( node . right ) + 1 ; } function checkRec ( root , n , res ) { if ( root == null ) return 0 ; var c = checkRec ( root . left , n , res ) + 1 + checkRec ( root . right , n , res ) ; if ( c == n - c ) res . res = true ; return c ; } function check ( root ) { var n = count ( root ) ; res = new Res ( ) ; checkRec ( root , n , res ) ; return res . res ; } root = new Node ( 5 ) ; root . left = new Node ( 1 ) ; root . right = new Node ( 6 ) ; root . left . left = new Node ( 3 ) ; root . right . left = new Node ( 7 ) ; root . right . right = new Node ( 4 ) ; if ( check ( root ) == true ) document . write ( " " ) ; else document . write ( " " ) ;