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¶
# 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)$
Stepbystep solution¶
Let's see the solution code stepbystep.
# 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)
# Output
s = Solution()
t_merged = s.mergeTrees(t1, t2)
if t1 and t2:¶
The first ifstatement determines if both input arguments t1
and t2
are not None
.
Both trees are not None
¶
t1
t2
t1 and t2
if t1 and t2:
print('true')
Either of tree is None
¶
# No output is generated
None and t2
# No print
if None and t2:
print('true')
if t1 and None:
print('true')
Both of tree is None
¶
# no output
None and None
# No print
if None and None:
print('true')
if statement is False
¶

t1 or t2
return "notNone
" object, if either of them is not None, and  if both is
None
, it will returnNone
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
print(f't1: {t1}')
print(f't2: {t2}')
return_or(t1, None)
return_or(None, t2)
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
 ifstatement with
[object] and [object]
 returnstatement 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