Merge Two Binary Trees

Merge two binary trees into a new binary tree.  The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Example:

Input: 
	Tree 1   
          1      
         / \     
        3   2    
       /         
      5          
	Tree 2   
          2      
         / \     
        1   3    
         \   \     
          4   7  
Output: 
Merged tree:
	     3      
	    / \
	   4   5
	  / \   \ 
	 5   4   7
Inorder: 5 4 4 3 5 7

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MergeTwoBinaryTrees {
    public static void main(String[] args) {
        // first tree
        TreeNode t1 = new TreeNode(1);
        t1.left = new TreeNode(3);
        t1.right = new TreeNode(2);
        t1.left.left = new TreeNode(5);

        // second tree
        TreeNode t2 = new TreeNode(2);
        t2.left = new TreeNode(1);
        t2.right = new TreeNode(3);
        t2.left.right = new TreeNode(4);
        t2.right.right = new TreeNode(7);

        TreeNode merge = mergeTrees(t1, t2);

        System.out.println("Inorder of merge Tree: ");
        inorder(merge);
        System.out.println(Arrays.asList(result));
    }

    // method to merge two tree
    private static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        // if first is empty
        // return second tree
        if (t1 == null)
            return t2;
        // if second is empty return first
        if (t2 == null)
            return t1;

        // store the sum of both the trees
        t1.val += t2.val;
        // call for left subtrees
        t1.left = mergeTrees(t1.left, t2.left);

        // call for right subtrees
        t1.right = mergeTrees(t1.right, t2.right);

        // return the merge tree
        return t1;
    }

    static List<Integer> result = new ArrayList<>();

    public static void inorder(TreeNode root) {
        if (root == null)
            return;

        // visit left node
        inorder(root.left);
        // Add root value
        result.add(root.val);
        // visit right node
        inorder(root.right);

    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
};

//function to merge two trees
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) 
{
    //if first is empty 
    //return second tree  
    if(t1==NULL)
              return t2;
    //if second is empty return first
     if(t2==NULL)
               return t1;

    //store the sum of both the trees 
    t1->data+=t2->data;
    //call for left subtrees
    t1->left=mergeTrees(t1->left,t2->left);

    //call for right subtrees
    t1->right=mergeTrees(t1->right,t2->right);

    //return the merge tree
    return t1;
}
//Function to find inorder Traversal
//of tree
void inorderTraversal(TreeNode *root)
{
    //Base Case
    if(root==NULL)
       return;
    //visit left subtree
    inorderTraversal(root->left);
    // visit root
    cout<<root->data<<" ";
    //visit right subtree
    inorderTraversal(root->right);
}
int main()
{
   //first tree
   TreeNode *t1=new TreeNode(1);
   t1->left=new TreeNode(3);
   t1->right=new TreeNode(2);
   t1->left->left=new TreeNode(5);

   //second tree
   TreeNode *t2=new TreeNode(2);
   t2->left=new TreeNode(1);
   t2->right=new TreeNode(3);
   t2->left->right=new TreeNode(4);
   t2->right->right=new TreeNode(7);

   TreeNode *merge=mergeTrees(t1,t2);
   
   cout<<"Inorder of merge Tree: ";
   inorderTraversal(merge);
   return 0;

}