617. Merge Two Binary Trees

Comments

Problem Setting

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.

Solution

In [8]:
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def mergeTrees(self, t1, t2):
        """
        :type t1: TreeNode
        :type t2: TreeNode
        :rtype: TreeNode
        """
        
        if t1 and t2:
            # Merge the values from two trees
            node = TreeNode(t1.val + t2.val)
            
            # Merge the left trees using the function recursively
            node.left = self.mergeTrees(t1.left, t2.left)
            
            # Merge the right trees using the function recursively
            node.right = self.mergeTrees(t1.right, t2.right)
            
            return node
            
        else:
            return t1 or t2

Complexity Analysis

  • Time Complexity $O (m)$

    all of the nodes will be searched but one time only. So it can be solved within linear based on the total number of nodes in the two trees m

  • Space complexity $O (m)$

Step-by-step solution

Let's see the solution code step-by-step.

In [9]:
# Example 1

# Left tree
t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.left.left = TreeNode(5)
t1.right = TreeNode(2)

# Right tree
t2 = TreeNode(2)
t2.left = TreeNode(1)
t2.left.right = TreeNode(4)
t2.right = TreeNode(3)
t2.right.right = TreeNode(7)
In [11]:
# Output
s = Solution()
t_merged = s.mergeTrees(t1, t2)

if t1 and t2:

The first if-statement determines if both input arguments t1 and t2 are not None.

Both trees are not None

In [14]:
t1
Out[14]:
<__main__.TreeNode at 0x10e687eb8>
In [15]:
t2
Out[15]:
<__main__.TreeNode at 0x10e6870b8>
In [16]:
t1 and t2
Out[16]:
<__main__.TreeNode at 0x10e6870b8>
In [13]:
if t1 and t2:
    print('true')

true

Either of tree is None

In [19]:
# No output is generated
None and t2
In [21]:
# No print
if None and t2:
    print('true')
    
if t1 and None:
    print('true')

Both of tree is None

In [24]:
# no output
None and None
In [25]:
# No print
if None and None:
    print('true')

if statement is False

  • t1 or t2 return "not None" object, if either of them is not None, and
  • if both is None , it will return None
In [32]:
def return_or(t1, t2):
    if t1 is None:
        return t1 or t2
    elif t2 is None:
        return t1 or t2
    elif (t1 is None) and (t2 is None):
        return t1 or t2
In [31]:
print(f't1: {t1}')
print(f't2: {t2}')

t1: <__main__.TreeNode object at 0x10e687eb8>
t2: <__main__.TreeNode object at 0x10e6870b8>
In [28]:
return_or(t1, None)
Out[28]:
<__main__.TreeNode at 0x10e687eb8>
In [29]:
return_or(None, t2)
Out[29]:
<__main__.TreeNode at 0x10e6870b8>
In [30]:
return_or(None, None)

if statement is True

In the example, "if statement is True" occurs only on the root node, which has both left and right nodes.

First the sum of each value from both nodes i.e., $1 + 2 = 3$ is stored at the root node in a merged tree. Then the left merged node is recursively obtained by node.left = self.mergeTrees(t1.left, t2.left). The same process occurs for the right node.

Conclusion

In this problem, we saw the usage of

  • if-statement with [object] and [object]
  • return-statement with [object] or [object]
  • a recursive function for tree

This problem seems to be simple but is interesting to see the power of recursive function. We tend to solve the problem related to tree, binary search by using this kind of recursive function with minimal lines of code.

Comments

Comments powered by Disqus