# 617. Merge Two Binary Trees

## 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 :
# 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 :
# 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 :
# 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 :
t1

Out:
<__main__.TreeNode at 0x10e687eb8>
In :
t2

Out:
<__main__.TreeNode at 0x10e6870b8>
In :
t1 and t2

Out:
<__main__.TreeNode at 0x10e6870b8>
In :
if t1 and t2:
print('true')

true


#### Either of tree is None¶

In :
# No output is generated
None and t2

In :
# No print
if None and t2:
print('true')

if t1 and None:
print('true')


#### Both of tree is None¶

In :
# no output
None and None

In :
# 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 :
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 :
print(f't1: {t1}')
print(f't2: {t2}')

t1: <__main__.TreeNode object at 0x10e687eb8>
t2: <__main__.TreeNode object at 0x10e6870b8>

In :
return_or(t1, None)

Out:
<__main__.TreeNode at 0x10e687eb8>
In :
return_or(None, t2)

Out:
<__main__.TreeNode at 0x10e6870b8>
In :
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.