Check if a given Binary Tree is height balanced like a Red | Helper function that allocates a new node with the given data and None left and right poers . ; Returns returns tree if the Binary tree is balanced like a Red - Black tree . This function also sets value in maxh and minh ( passed by reference ) . maxh and minh are set as maximum and minimum heights of root . ; Base case ; To store max and min heights of left subtree ; To store max and min heights of right subtree ; Check if left subtree is balanced , also set lmxh and lmnh ; Check if right subtree is balanced , also set rmxh and rmnh ; Set the max and min heights of this node for the parent call ; See if this node is balanced ; A wrapper over isBalancedUtil ( ) ; Driver Code
class newNode : NEW_LINE INDENT def __init__ ( self , key ) : NEW_LINE INDENT self . data = key NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def isBalancedUtil ( root , maxh , minh ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT maxh = minh = 0 NEW_LINE return True NEW_LINE DEDENT lmxh = 0 NEW_LINE lmnh = 0 NEW_LINE rmxh , rmnh = 0 , 0 NEW_LINE if ( isBalancedUtil ( root . left , lmxh , lmnh ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( isBalancedUtil ( root . right , rmxh , rmnh ) == False ) : NEW_LINE INDENT return False NEW_LINE DEDENT maxh = max ( lmxh , rmxh ) + 1 NEW_LINE minh = min ( lmnh , rmnh ) + 1 NEW_LINE if ( maxh <= 2 * minh ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def isBalanced ( root ) : NEW_LINE INDENT maxh , minh = 0 , 0 NEW_LINE return isBalancedUtil ( root , maxh , minh ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = newNode ( 10 ) NEW_LINE root . left = newNode ( 5 ) NEW_LINE root . right = newNode ( 100 ) NEW_LINE root . right . left = newNode ( 50 ) NEW_LINE root . right . right = newNode ( 150 ) NEW_LINE root . right . left . left = newNode ( 40 ) NEW_LINE if ( isBalanced ( root ) ) : NEW_LINE INDENT print ( " Balanced " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Balanced " ) NEW_LINE DEDENT DEDENT