Problem: You are given two binary trees root1 and root2. You need to merge them and return the merged tree (see example below).
Example 1:
Input: root1 = [1,2,2,6], root2 = [3,1,3,8,1,7]
Output: 4 3 5 14 1 7
Output: 4 3 5 14 1 7
Approach:
Simply recursion can be used to merge the binary trees. We will keep checking on whether we get any node which is null then we will return other node. After this, we will merge the values into any one tree node (say tree1) and call the recursion for the left of both trees, similarly call the recursion for the right of trees. At last return the merged node.
Code Implementation:
import java.util.LinkedList;
import java.util.Queue;
public class MergeBinaryTrees {
public static class Node {
int val;
Node left, right;
// Constructor
Node(int val) {
this.val = val;
left = right = null;
}
}
public static void main(String[] args) {
/*
* Creating Binary Tree The created binary tree is same as in the above given
* figure (refer figure for reference)
*/
/* Tree 1 */
Node root1 = new Node(1);
root1.left = new Node(2);
root1.right = new Node(2);
root1.left.left = new Node(6);
/* Tree 2 */
Node root2 = new Node(3);
root2.left = new Node(1);
root2.right = new Node(3);
root2.left.left = new Node(8);
root2.left.right = new Node(1);
root2.right.left = new Node(7);
mergeTrees(root1, root2);
/* megred tree is now Tree 1 having root as root1 */
/* printing the merged tree */
levelOrder(root1);
}
private static void levelOrder(Node root) {
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (queue.size() != 0) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node temp = queue.poll();
/* printing the values of merged tree */
System.out.print(temp.val + " ");
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
}
}
public static Node mergeTrees(Node node1, Node node2) {
// if node1 is null and node2 is null return null
if (node1 == null && node2 == null)
return null;
/* if node1 is null return node2 */
if (node1 == null)
return node2;
/* if node2 is null return node1 */
if (node2 == null)
return node1;
/* merging the trees value */
node1.val += node2.val;
node1.left = mergeTrees(node1.left, node2.left);
node1.right = mergeTrees(node1.right, node2.right);
return node1;
}
}
Output:
4 3 5 14 1 7
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).