Merge Two Binary Trees by doing Node Sum ( Recursive and Iterative ) | C # program to Merge Two Binary Trees ; 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 null 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 conthe first Binary Tree 1 / \ 2 3 / \ \ 4 5 6 ; Let us conthe second Binary Tree 4 / \ 1 7 / / \ 3 2 6
using System ; using System . Collections . Generic ; class GFG { public class Node { public int data ; public Node left , right ; } ; public class snode { public Node l , r ; } ; static Node newNode ( int data ) { Node new_node = new Node ( ) ; new_node . data = data ; new_node . left = new_node . right = null ; return new_node ; } static void inorder ( Node node ) { if ( node == null ) return ; inorder ( node . left ) ; Console . Write ( node . data + " ▁ " ) ; inorder ( node . right ) ; } static Node MergeTrees ( Node t1 , Node t2 ) { if ( t1 == null ) return t2 ; if ( t2 == null ) return t1 ; Stack < snode > s = new Stack < snode > ( ) ; snode temp = new snode ( ) ; temp . l = t1 ; temp . r = t2 ; s . Push ( temp ) ; snode n ; while ( s . Count != 0 ) { n = s . Peek ( ) ; s . Pop ( ) ; if ( n . l == null n . r == null ) continue ; n . l . data += n . r . data ; if ( n . l . left == null ) n . l . left = n . r . left ; else { snode t = new snode ( ) ; t . l = n . l . left ; t . r = n . r . left ; s . Push ( t ) ; } if ( n . l . right == null ) n . l . right = n . r . right ; else { snode t = new snode ( ) ; t . l = n . l . right ; t . r = n . r . right ; s . Push ( t ) ; } } return t1 ; } public static void Main ( String [ ] args ) { Node root1 = newNode ( 1 ) ; root1 . left = newNode ( 2 ) ; root1 . right = newNode ( 3 ) ; root1 . left . left = newNode ( 4 ) ; root1 . left . right = newNode ( 5 ) ; root1 . right . right = newNode ( 6 ) ; Node root2 = newNode ( 4 ) ; root2 . left = newNode ( 1 ) ; root2 . right = newNode ( 7 ) ; root2 . left . left = newNode ( 3 ) ; root2 . right . left = newNode ( 2 ) ; root2 . right . right = newNode ( 6 ) ; Node root3 = MergeTrees ( root1 , root2 ) ; Console . Write ( " The ▁ Merged ▁ Binary ▁ Tree ▁ is : STRNEWLINE " ) ; inorder ( root3 ) ; } }