Foldable Binary Trees | Utility function to create a new tree node ; Returns true if the given tree can be folded ; A utility function that checks if trees with roots as n1 and n2 are mirror of each other ; If both left and right subtrees are NULL , then return true ; If one of the trees is NULL and other is not , then return false ; Otherwise check if left and right subtrees are mirrors of their counterparts ; Driver code ; The constructed binary tree is 1 / \ 2 3 \ / 4 5
class newNode : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = self . right = None NEW_LINE DEDENT DEDENT def IsFoldable ( root ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return True NEW_LINE DEDENT return IsFoldableUtil ( root . left , root . right ) NEW_LINE DEDENT def IsFoldableUtil ( n1 , n2 ) : NEW_LINE INDENT if n1 == None and n2 == None : NEW_LINE INDENT return True NEW_LINE DEDENT if n1 == None or n2 == None : NEW_LINE INDENT return False NEW_LINE DEDENT d1 = IsFoldableUtil ( n1 . left , n2 . right ) NEW_LINE d2 = IsFoldableUtil ( n1 . right , n2 . left ) NEW_LINE return d1 and d2 NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = newNode ( 1 ) NEW_LINE root . left = newNode ( 2 ) NEW_LINE root . right = newNode ( 3 ) NEW_LINE root . left . right = newNode ( 4 ) NEW_LINE root . right . left = newNode ( 5 ) NEW_LINE if IsFoldable ( root ) : NEW_LINE INDENT print ( " Tree ▁ is ▁ foldable " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Tree ▁ is ▁ not ▁ foldable " ) NEW_LINE DEDENT DEDENT