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.

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

• Solution approach 1 : using  preorder traversal
• Solution approach 2: using  stack
• Solution approach 3: using  bfs traversal

Solution approach 1 : using  preorder traversal

Solution Idea

The idea is to visit each node of the input binary trees using preorder traversal and check their existence in both the trees. If current nodes in both trees are not null then we add their values and update the current node value in the first tree. At the end of the traversal, the first tree will be the output i.e. merged binary tree.

Solution Steps

• If any one of the trees is null, we return the root of the other tree as an output. Otherwise, we sum the root1 and root2 values and update the root1-value with that sum.
• By calling the same function, we recursively merge the left sub-tree of both trees and assign it with root1->left.
• By calling the same function, we recursively merge the right sub-tree of both trees and assign it with root1->right.
• Finally, we return the root of the merged tree i.e. root1.

Solution Pseudocode

TreeNode mergeTrees(TreeNode root1, TreeNode root2) 
 {
    if (root1 == null)
        return root2
    if (root2 == null)
        return root1
    root1->data = root1->data + root2->data
    root1->left = mergeTrees(root1->left, root2->left)
    root1->right = mergeTrees(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))

Solution approach 2: iterative postorder traversal using stack

Solution Idea

Now we can try to solve the problem by traversing both trees iteratively in a preorder fashion. The question here is to merge both trees so we track nodes of both trees simultaneously using stack. For this, each entry in the stack stores data in the form of a pair of nodes: {nodetree1​, nodetree2​}. Here, nodetree1​ and nodetree2​ are the nodes of the first tree and the second tree respectively.

Solution Steps

• We start by inserting the root nodes of both the trees onto the stack.

• Now we run a loop till the stack is not empty. At each step of iteration:

  1. We remove a node pair from the stack and update the corresponding node in the first tree with the sum of their values.
  2. If both the current nodes are NULL, we continue with popping the next pair of nodes from the stack.
  3. If the left child of the first tree is not NULL, we insert the left child of both the trees onto the stack.
  4. If the left child of the first tree is NULL, we append the left child of the second tree to the current node of the first tree.
  5. We continue the same process for the right child pair as well.
• By end of the loop, we return the root of the merged tree i.e. root1.

Solution Pseudocode

TreeNode mergeTrees(TreeNode root1, TreeNode root2) 
{
    if (root1 == null)
        return root2
    Stack <TreeNode[]> stack
    TreeNode[] temp = {root1, root2}
    stack.push(temp)
    while (!stack.isEmpty()) 
    {
        temp = stack->pop()
        if (temp[0] == null || temp[1] == null)
            continue
        temp[0]->val = temp[0]->val + temp[1]->val
        
        if (temp[0]->left == null)
            temp[0]->left = temp[1]->left
        else 
        {
            TreeNode[] curr = {temp[0]->left, temp[1]->left})
            stack.push(curr)
        }
        
        if (temp[0]->right == null)
            temp[0]->right = temp[1]->right
        else
        {
            curr = {temp[0]->right, temp[1]->right}
            stack.push(curr)
        }
    }
    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))

Solution approach 3: using  BFS or level order traversal

Solution Idea

One idea is clear: to merge both trees, we need to access each node of both trees in the same order and sum their corresponding node's values. So we can also think to solve this problem using BFS or level order traversal where we merge both trees in level by level fashion.

The implementation idea is quite similar to the above approach but we use the queue data structure to track the order of nodes and merge their values.

Solution Pseudocode

TreeNode mergeTrees(TreeNode root1, TreeNode root2) 
{
    if (root1 == null)
        return root2
    Queue <TreeNode[]> queue
    TreeNode[] temp = {root1, root2}
    queue.enqueue(temp)
    while (!stack.isEmpty()) 
    {
        temp = queue.dequeue()
        if (temp[0] == null || temp[1] == null)
            continue
        temp[0]->val = temp[0]->val + temp[1]->val
        
        if (temp[0]->left == null)
            temp[0]->left = temp[1]->left
        else 
        {
            TreeNode[] curr = {temp[0]->left, temp[1]->left})
            queue.enqueue(curr)
        }
        
        if (temp[0]->right == null)
            temp[0]->right = temp[1]->right
        else
        {
            curr = {temp[0]->right, temp[1]->right}
            queue.enqueue(curr)
        }
    }
    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 the inorder or postorder or morris traversal?
• Why are we taking the min(m, n) to calculate the time and space complexities?
• What would be the best and average-case time complexity of the above approaches?
• What would be the space complexity of the BFS approach?
• In the last two approaches, instead of if(temp[0] == null || temp[1] == null), can we use if(temp[1] == null)?

Suggested coding questions to practice

• Count half nodes in a Binary tree
• Count full nodes in a Binary tree
• Deepest right leaf node in a binary tree
• Get the level of a node in a binary tree
• Check if two trees are identical
• Print all nodes at distance K from a given node

Enjoy learning, Enjoy Algorithms