Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.You need to merge them 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 new tree.

Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7 

Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

 Source:LeetCode

Solution:

We traverse both trees in a preorder fashion. In each step, we check if both nodes isn't null, if so we add the value of the nodes; otherwise, we return the one that isn't null as a child of the first tree (t1). if in any case, it happens that the second tree (t2) has  reached leaf node then we return t1, and vice versa. At the end, the first tree (t1) will be the resultant tree which represent the merged tree.

Note: I haven't created  a new tree, I'm using the first tree to represent the final tree. However, doing so will follow similar approach as one shown below.

Complexity Analysis

• Time complexity : $O(m)$. $m$ nodes need to be traversed ($m$ represents the minimum number of nodes from the two given trees)
  
• Space complexity : $O(m)$. In average case, depth will be $.O(logm).$
  

 Recursive Solution:

 public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
     
        if(t1!=null && t2!=null)
            t1.val+= t2.val; //add the node's value
        else 
            return t1==null?t2:t1; //return appropriate node       
        
        t1.left =  mergeTrees(t1==null?null:t1.left,t2==null?null:t2.left);
        t1.right = mergeTrees(t1==null?null:t1.right,t2==null?null:t2.right);
        
        return t1;
    }