Merge Two Binary into a Single Binary Tree

Difficulty: Easy, Asked-in: Amazon, Adobe, Hike

Key takeaway: An excellent problem to learn problem-solving using iterative and recursive pre-order traversals.

Let’s understand the problem!

Given two binary trees with root nodes root1 and root2, write a program to merge them into a single binary tree.

• Imagine that when we put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
• The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the new value of the merged node.
• We need to return the root of the merged tree.
• The merging process must start from the root nodes of both trees.

Important note: before moving on to the solutions, we recommend trying this problem on paper for atleast 15 or 30 minutes. Enjoy problem-solving!

Examples

Input: 
     Tree 1            Tree 2                  
       6                3                            
      / \              / \                            
     4   4            6   1                        
    /                / \   \                      
   5                3   2   7

Output: Merged tree
         9
        / \
       10  5
      / \   \ 
     8  2   7

Discussed solution approaches

• Recursive approach using  preorder traversal
• Iterative approach by tracking pair of nodes using stack
• Iterative approach approach using  bfs traversal

Recursive approach using  preorder traversal

Solution idea

To merge two binary trees, we want to visit each node of the input trees and combine them in some way. One way to do this is to use a preorder traversal, which means that we visit the root of the tree, then the left child, and then the right child.

As we visit each node, we check if it exists in both trees. If the nodes exist in both trees, we add their values and update the current node value in the first tree. If one of the tree node is null, we update the current node value in the first tree with the value of other node.

By following this process for each node in the input trees, we can combine the trees into a single tree, where resulting tree will be the first tree.

Solution steps

1. Base case: If either of the input trees is null, we return the root of the other tree. Otherwise, we sum the values of the roots of the two trees and update the root of the first tree with this sum.

   if (root1 == NULL)
      return root2
      
   if (root2 == NULL)
      return root1
   
   root1->data = root1->data + root2->data

2. We recursively merge the left subtrees of the two trees by calling the same function and assign the resulting tree to the left child of the root of the first tree. root1->left = mergeBinaryTrees(root1->left, root2->left).
3. We recursively merge the right subtrees of the two trees by calling the same function and assign the resulting tree to the right child of the root of the first tree. root1->right = mergeBinaryTrees(root1->right, root2->right).
4. Return the root of the merged tree (i.e., the root of the first tree).

Solution code C++

TreeNode* mergeBinaryTrees(TreeNode* root1, TreeNode* root2) 
{
    if (root1 == NULL)
        return root2;
    
    if (root2 == NULL)
        return root1;
 
    root1->data = root1->data + root2->data;
    root1->left = mergeBinaryTrees(root1->left, root2->left);
    root1->right = mergeBinaryTrees(root1->right, root2->right);

    return root1;
}

Time and space complexity analysis

Suppose the number of nodes is m and n in both trees. So in the worst case, we recursively visit min(m, n) nodes and perform O(1) operations with each node. Time complexity = O(min(m, n))

In the worst case, the depth of the recursion tree can go up to min(m, n) in the case of a skewed tree. Space complexity = O(min(m, n))

Iterative approach by tracking pair of nodes using stack

Solution idea

The idea behind the solution is to iteratively traverse both trees in a preorder fashion, combining their nodes as we go. To do this, we will track nodes from both trees simultaneously using a stack, where each entry in the stack consists of a pair of nodes: {node from tree 1, node from tree 2}.

Solution steps

1. We start by checking if root1 is null. If it is, we return root2 since there is nothing to merge with. Otherwise, we push the pair {root1, root2} onto the stack and enter a loop that continues until the stack is empty.
2. Inside the loop, we pop the top pair of nodes from the stack and store them in the variable temp. We then check if either of the nodes in the pair is null. If either node is null, we skip the rest of the loop and continue with the next iteration. Otherwise, we add the values of the two nodes and update the value of the node from the first tree with this sum.
3. Next, we check the left children of the two nodes. If the left child of the first node is null, we set it to the left child of the second node. Otherwise, we push the pair {temp.first->left, temp.second->left} onto the stack. We do the same thing for the right children of the two nodes.
4. Finally, after the loop has finished executing, we return the root of the first tree, which is now the merged tree.

Solution Code C++

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 
{
    if (root1 == NULL)
        return root2;
    
    stack<pair<TreeNode*, TreeNode*>> stack;
    stack.push({root1, root2});
    
    while (stack.empty() == false) 
    {
        auto temp = stack.top();
        stack.pop();
        if (temp.first == NULL || temp.second == NULL)
            continue;
    
        temp.first->val = temp.first->val + temp.second->val;
        
        if (temp.first->left == NULL)
            temp.first->left = temp.second->left;
        else
            stack.push({temp.first->left, temp.second->left});
    
        if (temp.first->right == NULL)
            temp.first->right = temp.second->right;
        else
            stack.push({temp.first->right, temp.second->right});
    }
    
    return root1;
}

Time and space complexity analysis

Suppose the number of nodes is m and n in both trees. So in the worst case, we visit min(m, n) nodes and perform O(1) operations with each node. Time complexity = O(min(m, n))

In the worst case, the size of the stack space is min(m, n) (case of a skewed tree). Space complexity = O(min(m, n))

Iterative approach approach using  bfs traversal

Solution idea

The idea behind this solution is to merge both trees by accessing and summing the values of each corresponding node in the same order. One way to do this is using a breadth-first search (BFS) or level order traversal, where we merge the trees level by level.

To implement this solution, we can use a queue data structure to track the order of nodes and merge their values. This approach is similar to the previous solution, but instead of using a stack, we use a queue to track the nodes in a level-by-level fashion.

Solution steps

We start by checking if root1 is NULL. If it is, we return root2. Otherwise, we create a queue and insert a pair consisting of root1 and root2 into the queue.

Next, we run a loop that continues as long as the queue is not empty.

• Inside the loop, we retrieve the front pair of the queue and store it in a variable called temp. If either temp.first or temp.second is NULL, the loop continues to the next iteration without doing anything.
• If both temp.first and temp.second are not NULL, we sum their values and assign the result to temp.first->val.
• Then, we check if temp.first->left is NULL. If it is, we set temp.first->left to temp.second->left. Otherwise, we insert a pair consisting of temp.first->left and temp.second->left into the queue. We do the same thing for the right child nodes.

Finally, at the end of the loop, we return root1 as the output.

Solution code C++

TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) 
{
    if (root1 == NULL) 
        return root2;
        
    queue<pair<TreeNode*, TreeNode*>> queue;
    queue.emplace(root1, root2);
    
    while (queue.empty() == false) 
    {
        auto temp = queue.front();
        queue.pop();
        if (temp.first == NULL || temp.second == NULL) 
            continue;
        
        temp.first->val = temp.first->val + temp.second->val;
        
        if (temp.first->left == NULL)
            temp.first->left = temp.second->left;
        else
            queue.emplace(temp.first->left, temp.second->left);
            
        if (temp.first->right == NULL)
            temp.first->right = temp.second->right;
        else
            queue.emplace(temp.first->right, temp.second->right);
    }
    
    return root1;
}

Solution code Python

def mergeTrees(root1, root2):
    if not root1:
        return root2
    queue = collections.deque()
    queue.append((root1, root2))
    while queue:
        n1, n2 = queue.popleft()
        if not n1 or not n2:
            continue
        n1.val = n1.val + n2.val
        if not n1.left:
            n1.left = n2.left
        else:
            queue.append((n1.left, n2.left))
        if not n1.right:
            n1.right = n2.right
        else:
            queue.append((n1.right, n2.right))
    return root1

Time and space complexity analysis

Suppose the number of nodes is m and n in both trees. So in the worst case, we visit min(m, n) nodes and perform O(1) operations with each node. Time complexity = O(min(m, n))

Critical ideas to think!

• Can we try to solve this problem using inorder or postorder or Morris traversal?
• Why do we take the minimum of m and n to calculate the time and space complexities?
• What are the best-case and average-case time complexity of the above approaches?
• What is the space complexity of the BFS approach?
• Can we try to optimize the above approaches further?

Suggested coding questions to practice

• Merge Two Binary Trees
• Merge Two Binary Trees by Creating a New Tree
• Merge Two Binary Search Trees
• Merge Two N-ary Trees
• Merge Two Sorted Lists
• Merge Sorted Array
• Merge K-Sorted Lists
• Merge Intervals

Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!