Merge Two Binary Trees by doing Node Sum ( Recursive and Iterative ) | A binary tree node has data , pointer to left child and a pointer to right child ; Structure to store node pair onto stack ; Helper function that allocates a new node with the given data and None left and right pointers . ; Given a binary tree , print its nodes in inorder ; first recur on left child ; then print the data of node ; now recur on right child ; Function to merge given two binary trees ; Driver code ; Let us construct the first Binary Tree 1 / \ 2 3 / \ \ 4 5 6 ; Let us construct the second Binary Tree 4 / \ 1 7 / / \ 3 2 6
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 class snode : NEW_LINE INDENT def __init__ ( self , l , r ) : NEW_LINE INDENT self . l = l NEW_LINE self . r = r NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT new_node = Node ( data ) NEW_LINE return new_node NEW_LINE DEDENT def inorder ( node ) : NEW_LINE INDENT if ( not node ) : NEW_LINE INDENT return ; NEW_LINE DEDENT inorder ( node . left ) ; NEW_LINE print ( node . data , end = ' ▁ ' ) ; NEW_LINE inorder ( node . right ) ; NEW_LINE DEDENT def MergeTrees ( t1 , t2 ) : NEW_LINE INDENT if ( not t1 ) : NEW_LINE INDENT return t2 ; NEW_LINE DEDENT if ( not t2 ) : NEW_LINE INDENT return t1 ; NEW_LINE DEDENT s = [ ] NEW_LINE temp = snode ( t1 , t2 ) NEW_LINE s . append ( temp ) ; NEW_LINE n = None NEW_LINE while ( len ( s ) != 0 ) : NEW_LINE INDENT n = s [ - 1 ] NEW_LINE s . pop ( ) ; NEW_LINE if ( n . l == None or n . r == None ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT n . l . data += n . r . data ; NEW_LINE if ( n . l . left == None ) : NEW_LINE INDENT n . l . left = n . r . left ; NEW_LINE DEDENT else : NEW_LINE INDENT t = snode ( n . l . left , n . r . left ) NEW_LINE s . append ( t ) ; NEW_LINE DEDENT if ( n . l . right == None ) : NEW_LINE INDENT n . l . right = n . r . right ; NEW_LINE DEDENT else : NEW_LINE INDENT t = snode ( n . l . right , n . r . right ) NEW_LINE s . append ( t ) ; NEW_LINE DEDENT DEDENT return t1 ; 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 root1 . right . right = newNode ( 6 ) ; NEW_LINE root2 = newNode ( 4 ) ; NEW_LINE root2 . left = newNode ( 1 ) ; NEW_LINE root2 . right = newNode ( 7 ) ; NEW_LINE root2 . left . left = newNode ( 3 ) ; NEW_LINE root2 . right . left = newNode ( 2 ) ; NEW_LINE root2 . right . right = newNode ( 6 ) ; NEW_LINE root3 = MergeTrees ( root1 , root2 ) ; NEW_LINE print ( " The ▁ Merged ▁ Binary ▁ Tree ▁ is : " ) ; NEW_LINE inorder ( root3 ) ; NEW_LINE DEDENT