Find first non matching leaves in two binary trees | Utility function to create a new tree Node ; Prints the first non - matching leaf node in two trees if it exists , else prints nothing . ; If any of the tree is empty ; Create two stacks for preorder traversals ; If traversal of one tree is over and other tree still has nodes . ; Do iterative traversal of first tree and find first lead node in it as " temp1" ; pushing right childfirst so that left child comes first while popping . ; Do iterative traversal of second tree and find first lead node in it as " temp2" ; If we found leaves in both trees ; Driver Code
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 isLeaf ( t ) : NEW_LINE INDENT return ( ( t . left == None ) and ( t . right == None ) ) NEW_LINE DEDENT def findFirstUnmatch ( root1 , root2 ) : NEW_LINE INDENT if ( root1 == None or root2 == None ) : NEW_LINE INDENT return NEW_LINE DEDENT s1 = [ ] NEW_LINE s2 = [ ] NEW_LINE s1 . insert ( 0 , root1 ) NEW_LINE s2 . insert ( 0 , root2 ) NEW_LINE while ( len ( s1 ) or len ( s2 ) ) : NEW_LINE INDENT if ( len ( s1 ) == 0 or len ( s2 ) == 0 ) : NEW_LINE INDENT return NEW_LINE DEDENT temp1 = s1 [ 0 ] NEW_LINE s1 . pop ( 0 ) NEW_LINE while ( temp1 and not isLeaf ( temp1 ) ) : NEW_LINE INDENT s1 . insert ( 0 , temp1 . right ) NEW_LINE s1 . insert ( 0 , temp1 . left ) NEW_LINE temp1 = s1 [ 0 ] NEW_LINE s1 . pop ( 0 ) NEW_LINE DEDENT temp2 = s2 [ 0 ] NEW_LINE s2 . pop ( 0 ) NEW_LINE while ( temp2 and not isLeaf ( temp2 ) ) : NEW_LINE INDENT s2 . insert ( 0 , temp2 . right ) NEW_LINE s2 . insert ( 0 , temp2 . left ) NEW_LINE temp2 = s2 [ 0 ] NEW_LINE s2 . pop ( 0 ) NEW_LINE DEDENT if ( temp1 != None and temp2 != None ) : NEW_LINE INDENT if ( temp1 . data != temp2 . data ) : NEW_LINE INDENT print ( " First ▁ non ▁ matching ▁ leaves ▁ : " , temp1 . data , " " , temp2 . data ) NEW_LINE return NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root1 = newNode ( 5 ) NEW_LINE root1 . left = newNode ( 2 ) NEW_LINE root1 . right = newNode ( 7 ) NEW_LINE root1 . left . left = newNode ( 10 ) NEW_LINE root1 . left . right = newNode ( 11 ) NEW_LINE root2 = newNode ( 6 ) NEW_LINE root2 . left = newNode ( 10 ) NEW_LINE root2 . right = newNode ( 15 ) NEW_LINE findFirstUnmatch ( root1 , root2 ) NEW_LINE DEDENT