Check whether a given binary tree is perfect or not | Returns depth of leftmost leaf . ; This function tests if a binary treeis perfect or not . It basically checks for two things : 1 ) All leaves are at same level 2 ) All internal nodes have two children ; An empty tree is perfect ; If leaf node , then its depth must be same as depth of all other leaves . ; If internal node and one child is empty ; Left and right subtrees must be perfect . ; Wrapper over isPerfectRec ( ) ; Helper class that allocates a new node with the given key and None left and right pointer . ; Driver Code
def findADepth ( node ) : NEW_LINE INDENT d = 0 NEW_LINE while ( node != None ) : NEW_LINE INDENT d += 1 NEW_LINE node = node . left NEW_LINE DEDENT return d NEW_LINE DEDENT def isPerfectRec ( root , d , level = 0 ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( root . left == None and root . right == None ) : NEW_LINE INDENT return ( d == level + 1 ) NEW_LINE DEDENT if ( root . left == None or root . right == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT return ( isPerfectRec ( root . left , d , level + 1 ) and isPerfectRec ( root . right , d , level + 1 ) ) NEW_LINE DEDENT def isPerfect ( root ) : NEW_LINE INDENT d = findADepth ( root ) NEW_LINE return isPerfectRec ( root , d ) NEW_LINE DEDENT class newNode : NEW_LINE INDENT def __init__ ( self , k ) : NEW_LINE INDENT self . key = k NEW_LINE self . right = self . left = None NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = None NEW_LINE root = newNode ( 10 ) NEW_LINE root . left = newNode ( 20 ) NEW_LINE root . right = newNode ( 30 ) NEW_LINE root . left . left = newNode ( 40 ) NEW_LINE root . left . right = newNode ( 50 ) NEW_LINE root . right . left = newNode ( 60 ) NEW_LINE root . right . right = newNode ( 70 ) NEW_LINE if ( isPerfect ( root ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT