Merge two Binary Trees - Interview Problem

Difficulty: Easy

Asked in: Amazon, Microsoft

Understanding the Problem:

You are given two binary trees and you need to merge them into one binary tree.

To solve this problem, you can imagine putting one of the binary tree on top of the other in order to cover the other. Some of the nodes of the two trees will be overlapped while the others are not. Write a program to merge both the trees into a new binary tree.

Possible questions to ask the interviewer:

• Which node to keep in case of overlapping nodes? (Ans: You need to sum both the node’s value and use this value for node in merged tree.)
• What to do in case if one of the tree has NULL node? (Ans: Just keep the value of the second tree in the merged tree.)

For example:

Input 1:                                    Input 2:
         Tree 1                                Tree 1             

            1                                     5
           /  \                                  /  \
          3    2                                2    3
         /                                            \
        5                                              1

       Tree 2                                 Tree 2

           2                                     2
          /  \                                  /  
         1    3                                3 
          \    \                              /
           4    7                            1

Output:

       Merged tree:                         Merged tree:

           3                                   7
          / \                                 / \
         4   5                               5   3
        / \   \                             /     \
       5   4   7                           1       1

The solutions are below, why not to try it once before proceeding? Try it out here.

Solutions

We are going to discuss two solution approaches in this article. In the first approach, we will use recursion and the second one will be an iterative solution using stack.

• Recursive Solution
• Iterative Solution

Recursive Solution

Solution idea

We will start from the root node of both the trees and will traverse them in a preorder fashion. At each step of the traversal, we will compare the corresponding nodes of the trees. We will use recursion for proceeding to the next nodes. We will call the same method recursively for both left and right subtrees.

Solution steps

• Traverse both the trees T1 and T2 in preorder fashion.
• If the overlapping nodes in both the trees have not NULL values, we will update the first tree’s node value with the sum of the two values.
• If either of the corresponding nodes has NULL values, update the other node’s value into T1’s node.
• Recur for left and right subtrees
• Return the first tree T1’s root as it has the merged values from both the trees.

Pseudo-code

class treeNode
{
   int value
   treeNode left
   treeNode right
}

treeNode mergedBinaryTree(treeNode root1, treeNode root2)
{
     if(root1.value == NULL)
        return root2
     if(root2.value == NULL)
        return root1
     root1.value += root2.value
     root1.left = mergedBinaryTree(root1.left, root2.left)
     root1.right = mergedBinaryTree(root1.right, root1.right)
     return root1
}

Complexity Analysis

Time Complexity: O(M), here M represents the minimum of nodes(overlapping or non-overlapping) from both the tree.

Space Complexity: O(M) (The average case will be logM)

Critical ideas to think!

• What will be the condition for the worst-case space complexity of O(M)? (Hint: The space complexity is related to the depth of the tree.)

Iterative Solution

Solution idea

We need to compare the nodes of both the trees T1 and T2. For this we need to traverse all the nodes(minimum of the two). Here also we will traverse the trees but instead of using recursion, we will use stack to solve this problem iteratively.

Solution steps

• Create a stack S of type pair that will contain pair of both the trees.
• Push the root of both trees T1 and T2 into stack.
• While the stack is not empty keep popping out the elements.
• If the value of both the elements are present, sum them and update the value of T1’s node with the sum.
• If left or right child of both the trees are available, we will push them to stack.
• In case left or right child of T1 is missing, we will simply update it with T2’s corresponding node.
• If both left and right child are not available, we will continue popping the stack until it is empty.

Solution visualization

Pseudo-code

class treeNode
{
    int value
    treeNode left
    treeNode right
}
class treePair
{
    treeNode first
    treeNode second
}

treeNode mergedBinaryTree(treeNode root1, treeNode root2)
{
    if(root1 == NULL)
        return root2

   if(root2 == NULL)
        return root1

   stack <treePair> S  //stack S of type treePair
    treePair tree_pair
    tree_pair.first = root1
    tree_pair.second = root2
    S.push(tree_pair)
    while(not S.isEmpty())
    {
        treePair t = s.pop()
        if(t.first == NULL or t.second == NULL)
            continue
        t.first.value += t.second.value
        
        if(t.first.left == NULL)
        {
            t.first.left = t.second.left
        }
        else
        {
            tree_pair.first = t.first.left
            tree_pair.second = t.second.left
            S.push(tree_pair)
        }
        if(t.first.right == NULL)
        {
            t.first.right = t.second.right
        }
        else
        {
            tree_pair.first = t.first.right
            tree_pair.second = t.second.right
            S.push(tree_pair)
        }
        
    }
}

Complexity Analysis

Time Complexity: O(M), here M represents the minimum of nodes(overlapping or non-overlapping) from both the tree.

Space Complexity: O(M) (The average case will be logM)

Critical ideas to think!

• Can you think of other tree problems that can be solved iteratively using stack?

Comparison of Different Solutions

Suggested Problems to Solve

• Merge two binary search trees.
• Check if two binary trees are mirrors of each other or not.
• Iterative search for a key ‘x’ in a binary tree.
• Check if two binary trees are identical or not? (Try doing it iteratively for sure)
• Count the number of binary search trees present in a binary tree.

Happy Coding!

Team AfterAcademy!!