Merge Two Binary Tree into a Single Binary Tree

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

Key takeaway: An excellent problem to learn problem-solving using pre-order and level order.

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

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

Using  preorder traversal

Solution idea

To merge two binary trees, we need to process the nodes at matching positions in both trees. So we traverse each position in both trees simultaneously using preorder. At each position:

  • If both nodes exist, add their values and store the sum in the corresponding node of the first tree.
  • If only one node exists, use that node and its subtree in the merged tree.
  • If both nodes are null, there is nothing to merge at that position.

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

  • 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.
  • We recursively merge the left subtrees 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).
  • We recursively merge the right subtrees 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).
  • Return the root of the merged tree (i.e., the root of the first tree).

Solution pseudocode

mergeBinaryTrees(root1, root2)
    if root1 is null
        return root2

    if root2 is null
        return root1

    // Both nodes exist, so combine their values
    root1.data = root1.data + root2.data

    // Recursively merge the left and right subtrees
    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). 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 preorder, 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}. Here each pair represents nodes at the same position in the two trees.

Solution steps

  1. We check 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 pair of nodes from the stack. We check if either of the nodes in the pair is null. If either node is null, we skip that pair and continue with the next iteration. Otherwise, we add the values of the nodes and update the value of the node from the first tree with this sum.
  3. Now 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 {node1.left, node2.left} onto the stack. We do the same thing for the right child of the first node. In other words: If the first tree has no child, we attach the corresponding child from the second tree directly. Otherwise, we push that pair onto the stack for later processing.
  4. Finally, after the loop, we return the root of the first tree.

Solution pseudocode

mergeTrees(root1, root2)
    if root1 is null
        return root2

    stack = empty stack
    push (root1, root2) onto stack

    while stack is not empty
        (node1, node2) = top of stack
        pop stack

        if node1 is null or node2 is null
            continue

        node1.val = node1.val + node2.val

        if node1.left is null
            node1.left = node2.left
        else
            push (node1.left, node2.left) onto stack

        if node1.right is null
            node1.right = node2.right
        else
            push (node1.right, node2.right) onto stack

    return root1

Time and space complexity analysis

Suppose 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 using  BFS traversal

Solution idea

The idea behind this is to merge both trees by accessing and adding the values of each corresponding node. One way to do this is using breadth-first search traversal, where we merge the trees level by level. To implement this, we can use a queue 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 nodes.

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.

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

  • Inside the loop, we remove the front pair of nodes from the queue. If either node is NULL, loop continues to the next iteration without doing anything.
  • If both nodes are not NULL, we sum their values and assign the result to the first node.
  • Now we check if the left child of the first node is null. If it is, we set it to the left child of the second node. Otherwise, we push the pair {node1.left, node2.left} onto the stack. We do the same thing for the right child of the first node.

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

Solution pseudocode

mergeTrees(root1, root2)
    if root1 is null
        return root2

    queue = empty queue
    enqueue (root1, root2)

    while queue is not empty
        (node1, node2) = front of queue
        dequeue queue

        if node1 is null or node2 is null
            continue

        node1.val = node1.val + node2.val

        if node1.left is null
            node1.left = node2.left
        else
            enqueue (node1.left, node2.left)

        if node1.right is null
            node1.right = node2.right
        else
            enqueue (node1.right, node2.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!

Find us on:

Self-paced Courses and Blogs