Check if all levels of two trees are anagrams or not | Returns true if trees with root1 and root2 are level by level anagram , else returns false . ; Base Cases ; start level order traversal of two trees using two queues . ; n1 ( queue size ) indicates number of Nodes at current level in first tree and n2 indicates number of nodes in current level of second tree . ; If n1 and n2 are different ; If level order traversal is over ; Dequeue all Nodes of current level and Enqueue all Nodes of next level ; Check if nodes of current levels are anagrams or not . ; Utility function to create a new tree Node ; Driver Code ; Constructing both the trees .
def areAnagrams ( root1 , root2 ) : NEW_LINE INDENT if ( root1 == None and root2 == None ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( root1 == None or root2 == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT q1 = [ ] NEW_LINE q2 = [ ] NEW_LINE q1 . append ( root1 ) NEW_LINE q2 . append ( root2 ) NEW_LINE while ( 1 ) : NEW_LINE INDENT n1 = len ( q1 ) NEW_LINE n2 = len ( q2 ) NEW_LINE if ( n1 != n2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n1 == 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT curr_level1 = [ ] NEW_LINE curr_level2 = [ ] NEW_LINE while ( n1 > 0 ) : NEW_LINE INDENT node1 = q1 [ 0 ] NEW_LINE q1 . pop ( 0 ) NEW_LINE if ( node1 . left != None ) : NEW_LINE INDENT q1 . append ( node1 . left ) NEW_LINE DEDENT if ( node1 . right != None ) : NEW_LINE INDENT q1 . append ( node1 . right ) NEW_LINE DEDENT n1 -= 1 NEW_LINE node2 = q2 [ 0 ] NEW_LINE q2 . pop ( 0 ) NEW_LINE if ( node2 . left != None ) : NEW_LINE INDENT q2 . append ( node2 . left ) NEW_LINE DEDENT if ( node2 . right != None ) : NEW_LINE INDENT q2 . append ( node2 . right ) NEW_LINE DEDENT curr_level1 . append ( node1 . data ) NEW_LINE curr_level2 . append ( node2 . data ) NEW_LINE DEDENT curr_level1 . sort ( ) NEW_LINE curr_level2 . sort ( ) NEW_LINE if ( curr_level1 != curr_level2 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT 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 if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root1 = newNode ( 1 ) NEW_LINE root1 . left = newNode ( 3 ) NEW_LINE root1 . right = newNode ( 2 ) NEW_LINE root1 . right . left = newNode ( 5 ) NEW_LINE root1 . right . right = newNode ( 4 ) 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 areAnagrams ( root1 , root2 ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT