Check if leaf traversal of two Binary Trees is same ? | Binary Tree node ; checks if a given node is leaf or not . ; Returns true of leaf traversal of two trees is same , else false ; Create empty stacks . These stacks are going to be used for iterative traversals . ; Loop until either of two stacks is not empty ; If one of the stacks is empty means other stack has extra leaves so return false ; append right and left children of temp1 . Note that right child is inserted before left ; same for tree2 ; If one is None and other is not , then return false ; If both are not None and data is not same return false ; If control reaches this point , all leaves are matched ; Driver Code ; Let us create trees in above example 1
class Node : NEW_LINE INDENT def __init__ ( self , x ) : NEW_LINE INDENT self . data = x NEW_LINE self . left = self . right = None NEW_LINE DEDENT def isLeaf ( self ) : NEW_LINE INDENT return ( self . left == None and self . right == None ) NEW_LINE DEDENT DEDENT def isSame ( root1 , root2 ) : NEW_LINE INDENT s1 = [ ] NEW_LINE s2 = [ ] NEW_LINE s1 . append ( root1 ) NEW_LINE s2 . append ( root2 ) NEW_LINE while ( len ( s1 ) != 0 or len ( s2 ) != 0 ) : NEW_LINE INDENT if ( len ( s1 ) == 0 or len ( s2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT temp1 = s1 . pop ( - 1 ) NEW_LINE while ( temp1 != None and not temp1 . isLeaf ( ) ) : NEW_LINE INDENT if ( temp1 . right != None ) : NEW_LINE INDENT s1 . append ( temp1 . right ) NEW_LINE DEDENT if ( temp1 . left != None ) : NEW_LINE INDENT s1 . append ( temp1 . left ) NEW_LINE temp1 = s1 . pop ( - 1 ) NEW_LINE DEDENT DEDENT temp2 = s2 . pop ( - 1 ) NEW_LINE while ( temp2 != None and not temp2 . isLeaf ( ) ) : NEW_LINE INDENT if ( temp2 . right != None ) : NEW_LINE INDENT s2 . append ( temp2 . right ) NEW_LINE DEDENT if ( temp2 . left != None ) : NEW_LINE INDENT s2 . append ( temp2 . left ) NEW_LINE DEDENT temp2 = s2 . pop ( - 1 ) NEW_LINE DEDENT if ( temp1 == None and temp2 != None ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( temp1 != None and temp2 == None ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( temp1 != None and temp2 != None ) : NEW_LINE INDENT if ( temp1 . data != temp2 . data ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root1 = Node ( 1 ) NEW_LINE root1 . left = Node ( 2 ) NEW_LINE root1 . right = Node ( 3 ) NEW_LINE root1 . left . left = Node ( 4 ) NEW_LINE root1 . right . left = Node ( 6 ) NEW_LINE root1 . right . right = Node ( 7 ) NEW_LINE root2 = Node ( 0 ) NEW_LINE root2 . left = Node ( 1 ) NEW_LINE root2 . right = Node ( 5 ) NEW_LINE root2 . left . right = Node ( 4 ) NEW_LINE root2 . right . left = Node ( 6 ) NEW_LINE root2 . right . right = Node ( 7 ) NEW_LINE if ( isSame ( root1 , root2 ) ) : NEW_LINE INDENT print ( " Same " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Not ▁ Same " ) NEW_LINE DEDENT DEDENT