Merge Two Binary Trees

About the Problem:

In this question, we are supplied with two binary trees with TreeNode root1 and root2. Imagine putting one binary tree on top of another and where there are two nodes, the resultant nodes have the summation of these two nodes, otherwise a NULL node is taken within the tree which missed one node.

TreeNode structure:

1
2
3
4
5
struct Treenode {
  int val;
  Treenode * left;
  Treenode * right;
};

Example 1:

Input: root1= [ 4, 5, null, 8, 7, 9 ], root2 = [ 2, null, 1, 3, 6 ]

Output: [ 6, 16, null, 9, 10, 9, 6 ]

Example 2:

Input: root1= [ 1, 8, 7 ,null, 10, null, 15, 18 ], root2 = [ 3, 10, 4, null, 19, null, null, 17, 6 ]

Output: [ 4, 18, 11, null, 29, null, 15, 35, 6 ]

In this article, we are defining two approaches; one is using recursion and the second is iterative using stack.

Approach #1: Recursion Solution

We can start traversing from the root node of both the trees ( root1 and root2 ) in a preorder function. At each call we first check if both current TreeNodes are NULL or not. If not, we return NULL as none of them have any value associated with it. When it comes to one TreeNode being NULL we return the other TreeNode, and in the case of both current TreeNode not being NULL we add both values and update the value of the first tree. Next, we pass assign left pointer of root1 to function call of the same function using the left pointer of both the trees. The same goes for the right pointer of root1.

Algorithm:

• In preorder fashion traverse both the binary trees, i.e, tree1 and tree2.

• If both the current treenodes are NULL, return NULL.

• If one of them isn’t NULL, return the other treenode.

• If both are not NULL, update the first tree, i.e, tree1, with the summation of values of both the treenodes.

• Make the recursive call for left subtree and right subtree.

• At last, return the treenode of tree1, as it contains the merged version of both trees.

Code Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
Treenode * mergeTrees(Treenode * root1, Treenode * root2) {
  if (!root1 && !root2) return NULL;
  if (!root1) return root2;
  if (!root2) return root1;

  root1 - > val = root1 - > val + root2 - > val;

  root1 - > left = mergeTrees(root1 - > left, root2 - > left);
  root1 - > right = mergeTrees(root1 - > right, root2 - > right);

  return root1;
}

Time Complexity: O(n), we visit each treenode of both the binary trees. Here n is the minimum number of nodes given two trees.

Space Complexity: O(n), mainly happens in the case of skewed trees where we have to make calls for each node at each level and an average of O(logn) complexity.

Approach #2: Iterative Solution
In this approach, we’ll use the stack data structure to resolve, so as to avoid wasting recursion calls. At each step we push the worth of both the present Treenodes in terms of pairs. Val1 and val2 represent the nodes of tree1 and tree2 respectively. At each step we remove one pair from the stack and update tree1 in keeping with values within the pair. If the left and right pointer of tree1 isn’t NULL we push them into the stack. If the left child of tree1 is NULL, we update it with the left pointer of tree2. The same goes for the right pointer.

Algorithm:

• Create a stack of type pair< TreeNode*, Treenode*> containing the pointer of both trees.

• Push the root nodes of both the trees (tree1, tree2) into the stack.

• Pop elements from the stack one by one.

• Update the tree1 pointer with the sum of the pair node value.

• If the left pointer of tree1 is NULL then we assign the pointer with the left pointer of tree2, and the same goes for the right pointer.

• If the left pointer is not NULL, we push the pair of the left pointers of both the trees. The same goes for the right pointer.

• Finally, return the treenode of tree1, as it contains the merged version of both trees.

Code Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Treenode * mergeTrees(Treenode * root1, Treenode * root2) {

  if (root1 == NULL) {
    return root2;
  }
  stack < pair < Treenode * , Treenode * >> s;
  s.push({
    root1,
    root2
  });

  while (!s.empty()) {
    pair < Treenode * , Treenode * > curr = s.top();
    s.pop();

    if (curr.first == NULL || curr.second == NULL) continue;

    curr.first - > val += curr.second - > val;

    if (curr.first - > left == NULL)
      curr.first - > left = curr.second - > left;
    else
      s.push({
        curr.first - > left,
        curr.second - > left
      });

    if (curr.first - > right == NULL)
      curr.first - > right = curr.second - > right;
    else
      s.push({
        curr.first - > right,
        curr.second - > right
      });

  }
  return root1;
}

Time Complexity: O(n), we visit each treenode of both the binary trees. Here n is the minimum number of nodes given two trees.

Space Complexity: O(n), mainly happens in the case of skewed trees where we have to push n nodes to stack and an average of O(logn) complexity.