Tree Isomorphism Problem | A Binary tree node ; Check if the binary tree is isomorphic or not ; Both roots are None , trees isomorphic by definition ; Exactly one of the n1 and n2 is None , trees are not isomorphic ; There are two possible cases for n1 and n2 to be isomorphic Case 1 : The subtrees rooted at these nodes have NOT been " Flipped " . Both of these subtrees have to be isomorphic , hence the && Case 2 : The subtrees rooted at these nodes have been " Flipped " ; Let us create trees shown in above diagram
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def isIsomorphic ( n1 , n2 ) : NEW_LINE INDENT if n1 is None and n2 is None : NEW_LINE INDENT return True NEW_LINE DEDENT if n1 is None or n2 is None : NEW_LINE INDENT return False NEW_LINE DEDENT if n1 . data != n2 . data : NEW_LINE INDENT return False NEW_LINE DEDENT return ( ( isIsomorphic ( n1 . left , n2 . left ) and isIsomorphic ( n1 . right , n2 . right ) ) or ( isIsomorphic ( n1 . left , n2 . right ) and isIsomorphic ( n1 . right , n2 . left ) ) ) NEW_LINE DEDENT n1 = Node ( 1 ) NEW_LINE n1 . left = Node ( 2 ) NEW_LINE n1 . right = Node ( 3 ) NEW_LINE n1 . left . left = Node ( 4 ) NEW_LINE n1 . left . right = Node ( 5 ) NEW_LINE n1 . right . left = Node ( 6 ) NEW_LINE n1 . left . right . left = Node ( 7 ) NEW_LINE n1 . left . right . right = Node ( 8 ) NEW_LINE n2 = Node ( 1 ) NEW_LINE n2 . left = Node ( 3 ) NEW_LINE n2 . right = Node ( 2 ) NEW_LINE n2 . right . left = Node ( 4 ) NEW_LINE n2 . right . right = Node ( 5 ) NEW_LINE n2 . left . right = Node ( 6 ) NEW_LINE n2 . right . right . left = Node ( 8 ) NEW_LINE n2 . right . right . right = Node ( 7 ) NEW_LINE print " Yes " if ( isIsomorphic ( n1 , n2 ) == True ) else " No " NEW_LINE