Merge Two Binary Trees

Easy
0/40
Average time to solve is 15m
5 upvotes
Asked in companies
Thought WorksAppleGrab

Problem statement

You are given roots of two binary trees, ‘ROOT1’ and ‘ROOT2’. You need to merge the two trees into a new binary tree. The merge rule is that if the two nodes overlap, then the sum of the two nodes 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. Your task is to return the merged tree i.e. head of the new tree.

Note:

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

For example,

‘ROOT1’ = [1, 2, -1, -1, 3, -1, -1]  ‘ROOT2’ = [3, -1, -1].
The final tree would look like : [3, 2, -1, -1, 3, -1, -1], and the output will be printed in a pre-order way: 4 2 3.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

In the next 2*T lines, the first line of each test case contains space-separated integers denoting the nodes of the first binary tree, where -1 indicates that the NULL pointer has been appointed to the previous node 

The second line of each test case contains space-separated integers denoting the nodes of the second binary tree, where -1 indicates that the NULL pointer has been appointed to the previous node. 

The input is given in a preorder way, that is, the node then left subtree, and then right subtree as shown in the example.

Output format :

For each test case, return the resultant binary tree in a pre-order way.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T  <= 5
1 <= N <= 10^3
-10^3 <= DATA <= 10^3

Time Limit: 1 second

Sample Input 1 :

2
1 2 3 -1 -1 -1 -1
3 -1 -1
1 2 -1 -1 -1
1 -1 3 -1 -1

Sample Output 1 :

4 2 3 
2 2 3

Explanation of the Sample Input 1:

For the first test case:
The root node is 1 in ‘root1’ and  3 in ‘root2’, and the left child of ‘root1’ is 2, and the right child of ‘root1’ is 3. Therefore the resulting tree in preorder will be 4 2 3.


For the second test case:
The root node of root1 is 1 and for root2 is 1, the left child of root1 is 2, and right child is NULL, the left child of root2 is NULL, and the right child is 3; therefore, after merging trees, the preorder will be 2 2 3.

Sample Input 2 :

2
1 -1 -1
68 -1 -1
4 1 -1 -1 -1
1 -1 2 -1 -1

Sample Output 2 :

69 
5 1 2
Hint

Think of a recursive approach.

Approaches (2)
Use recursion

The main idea is to use recursion to traverse the tree in a Pre-order way. If any of the nodes is null, return the other node, and if both are NULL, return NULL.

 

  • We can traverse both the given trees in a preorder fashion. We check if the current node exists for both the trees.
  • We add the values in the current nodes of both the trees and update the value in the current node of the first tree to reflect this sum obtained.
  • If at any step one of these children happens to be null, we return the child of the other tree(representing the corresponding child subtree) to be added as a child subtree to the calling parent node in the first tree.
  • In the end, the first tree will represent the required resultant merged binary tree.
Time Complexity

O(N), where N is the Number of Nodes in the tree.

 

Since we are going through all the nodes of the tree, Hence net time complexity will be O( N ).

Space Complexity

O(N), where N is the Number of Nodes in the tree.

 

Since we are using recursion, hence N call-stacks would be made.

Code Solution
(100% EXP penalty)
Merge Two Binary Trees
Full screen
Console