Merge Two Binary Trees

Patrick Leaton
Published: April 5, 2021, 4:12 a.m.
Problem Description

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.

You need to merge them into a new binary tree. 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 node of new tree.

Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

 

Note: The merging process must start from the root nodes of both trees.

 

The description was taken from https://leetcode.com/problems/merge-two-binary-trees/.

Problem Solution

#Iterative
#O(N) Time, O(N) Space
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 is None:
            return t2                
        stack = []
        stack.append((t1,t2))
        while stack:
            node_one, node_two = stack.pop()
            if node_two is None:
                continue
            node_one.val += node_two.val
            if node_one.left is None:
                node_one.left = node_two.left
            else:
                stack.append((node_one.left,node_two.left))
            if node_one.right is None:
                node_one.right = node_two.right
            else:
                stack.append((node_one.right,node_two.right))     
        return t1
 
#Recursive
#O(M) Time, O(M) Space
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        t1.val += t2.val
        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)
        return t1

Problem Explanation

Iterative Solution

We can solve this problem with a Depth First Search traversal where we throw the second tree node's value onto the first tree node's value.

For this problem, we can stop adding values to the stack and essentially stop our DFS of a branch whenever we encounter the first node from the first tree that is null when the node from the other tree isn't because we won't have to continue searching down the null branch.  Whenever that happens, we will just duct tape the non-null node to the null one and will be done merging the branch.

Let's start by checking if the first input tree root is null, if it is then we will just return the second tree.

        if t1 is None:
            return t2         

 

Next, we will initialize our stack and append both tree roots to it.

        stack = []
        stack.append((t1,t2))

 

We will then create a stack that will run while there are still nodes in it that we need to merge.

         while stack:

 

During each iteration, we will pop a node from t1 and t2 off the stack.

            node_one, node_two = stack.pop()

 

We will need to check if the second tree's node is null so that we don't get a type error if we try to add its value to the first tree's node. 

            if node_two is None:
                continue

 

Next, we will add the second tree's node value to the first tree's node.

            node_one.val += node_two.val

 

If the first tree node's left child is null, we will use the second tree's node as the child.

            if node_one.left is None:
                node_one.left = node_two.left

 

If the first tree node's left child is not null, we will throw both tree nodes' left children onto the stack.

            else:
                stack.append((node_one.left,node_two.left))

 

We will then do the same thing, but for the right children.

            if node_one.right is None:
                node_one.right = node_two.right
            else:
                stack.append((node_one.right,node_two.right))     
 

Once both trees have been merged into the first tree, we will return the first tree's root.

        return t1

Recursive Solution

The recursive solution is a lot shorter, but we'll still traverse the tree in a similar DFS manner.

During each recursive call, we will check if one of the nodes is null.  If it is, we will return the other node.  If one node is null and the other one isn't, we are merging the branch of the non-null node's children.  If both are null, the branch is null.

        if t1 is None:
            return t2
        if t2 is None:
            return t1

 

Afterward, if neither of the nodes is null, we will add the second tree node's value to the first tree node.

        t1.val += t2.val

 

After adding the value, we will recurse the mergeTrees function on the first tree's left and right children.

        t1.left = self.mergeTrees(t1.left, t2.left)
        t1.right = self.mergeTrees(t1.right, t2.right)

 

Once both trees have been merged into the first tree, we will return the first tree's root.

This is a postorder traversal because each child node will be visited and merged before parent nodes.

        return t1