Last Updated: 17 Mar, 2021
Merge Two Binary Trees
Easy
Asked in companies
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.
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
Approaches
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.
The main idea is to use the stack to traverse the tree instead of using recursion.
We start by pushing the root nodes of both the trees onto the stack.
- At every step, we remove a node pair from the top of the stack. For every node pair removed, we add the values corresponding to the two nodes and update the value of the corresponding node in the first tree.
- Then, if the left child of the first tree exists, we push the left child (pair) of both the trees onto the stack. If the left child of the first tree doesn't exist, we append the left child (subtree) of the second tree to the current node of the first tree. We do the same for the right child pair as well.
- If at any step, both the current nodes are null, we continue with popping the next nodes from the stack.
- In the end, the first tree will represent the required resultant merged binary tree.
Similar problems