Iterative function to check if two trees are identical | Iterative Python3 program to check if two trees are identical ; Utility function to create a new tree node ; Iterative method to find height of Binary Tree ; Return true if both trees are empty ; Return false if one is empty and other is not ; Create an empty queues for simultaneous traversals ; Enqueue Roots of trees in respective queues ; Get front nodes and compare them ; Remove front nodes from queues ; Enqueue left children of both nodes ; If one left child is empty and other is not ; Right child code ( Similar to left child code ) ; Driver Code
from queue import Queue NEW_LINE 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 areIdentical ( root1 , root2 ) : NEW_LINE INDENT if ( root1 and root2 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( root1 or root2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT q1 = Queue ( ) NEW_LINE q2 = Queue ( ) NEW_LINE q1 . put ( root1 ) NEW_LINE q2 . put ( root2 ) NEW_LINE while ( not q1 . empty ( ) and not q2 . empty ( ) ) : NEW_LINE INDENT n1 = q1 . queue [ 0 ] NEW_LINE n2 = q2 . queue [ 0 ] NEW_LINE if ( n1 . data != n2 . data ) : NEW_LINE INDENT return False NEW_LINE DEDENT q1 . get ( ) NEW_LINE q2 . get ( ) NEW_LINE if ( n1 . left and n2 . left ) : NEW_LINE INDENT q1 . put ( n1 . left ) NEW_LINE q2 . put ( n2 . left ) NEW_LINE DEDENT elif ( n1 . left or n2 . left ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n1 . right and n2 . right ) : NEW_LINE INDENT q1 . put ( n1 . right ) NEW_LINE q2 . put ( n2 . right ) NEW_LINE DEDENT elif ( n1 . right or n2 . right ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root1 = newNode ( 1 ) NEW_LINE root1 . left = newNode ( 2 ) NEW_LINE root1 . right = newNode ( 3 ) NEW_LINE root1 . left . left = newNode ( 4 ) NEW_LINE root1 . left . right = newNode ( 5 ) NEW_LINE root2 = newNode ( 1 ) NEW_LINE root2 . left = newNode ( 2 ) NEW_LINE root2 . right = newNode ( 3 ) NEW_LINE root2 . left . left = newNode ( 4 ) NEW_LINE root2 . left . right = newNode ( 5 ) NEW_LINE if areIdentical ( root1 , root2 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT