Check if removing an edge can divide a Binary Tree in two halves | Python3 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 bool res = false ; ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . key = x NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def count ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT return ( count ( node . left ) + count ( node . right ) + 1 ) NEW_LINE DEDENT def checkRec ( root , n ) : NEW_LINE INDENT global res NEW_LINE if ( root == None ) : NEW_LINE return 0 NEW_LINE c = ( checkRec ( root . left , n ) + 1 + checkRec ( root . right , n ) ) NEW_LINE if ( c == n - c ) : NEW_LINE INDENT res = True NEW_LINE DEDENT return c NEW_LINE DEDENT def check ( root ) : NEW_LINE INDENT n = count ( root ) NEW_LINE checkRec ( root , n ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT res = False NEW_LINE root = Node ( 5 ) NEW_LINE root . left = Node ( 1 ) NEW_LINE root . right = Node ( 6 ) NEW_LINE root . left . left = Node ( 3 ) NEW_LINE root . right . left = Node ( 7 ) NEW_LINE root . right . right = Node ( 4 ) NEW_LINE check ( root ) NEW_LINE if res : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT