Python/data_structures/binary_tree/merge_two_binary_trees.py at master · manmita/Python · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#!/usr/local/bin/python3
"""
Problem Description: Given two binary tree, return the merged tree.
The rule for merging is that if two nodes overlap, then put the value sum of
both nodes to the new value of the merged node. Otherwise, the NOT null node
will be used as the node of new tree.
"""
from __future__ importannotations


classNode:
"""
 A binary node has value variable and pointers to its left and right node.
 """

def__init__(self, value: int=0) ->None:
self.value=value
self.left: Node|None=None
self.right: Node|None=None


defmerge_two_binary_trees(tree1: Node|None, tree2: Node|None) ->Node|None:
"""
 Returns root node of the merged tree.

 >>> tree1 = Node(5)
 >>> tree1.left = Node(6)
 >>> tree1.right = Node(7)
 >>> tree1.left.left = Node(2)
 >>> tree2 = Node(4)
 >>> tree2.left = Node(5)
 >>> tree2.right = Node(8)
 >>> tree2.left.right = Node(1)
 >>> tree2.right.right = Node(4)
 >>> merged_tree = merge_two_binary_trees(tree1, tree2)
 >>> print_preorder(merged_tree)
 9
 11
 2
 1
 15
 4
 """
iftree1isNone:
returntree2
iftree2isNone:
returntree1

tree1.value=tree1.value+tree2.value
tree1.left=merge_two_binary_trees(tree1.left, tree2.left)
tree1.right=merge_two_binary_trees(tree1.right, tree2.right)
returntree1


defprint_preorder(root: Node|None) ->None:
"""
 Print pre-order traversal of the tree.

 >>> root = Node(1)
 >>> root.left = Node(2)
 >>> root.right = Node(3)
 >>> print_preorder(root)
 1
 2
 3
 >>> print_preorder(root.right)
 3
 """
ifroot:
print(root.value)
print_preorder(root.left)
print_preorder(root.right)


if__name__=="__main__":
tree1=Node(1)
tree1.left=Node(2)
tree1.right=Node(3)
tree1.left.left=Node(4)

tree2=Node(2)
tree2.left=Node(4)
tree2.right=Node(6)
tree2.left.right=Node(9)
tree2.right.right=Node(5)

print("Tree1 is: ")
print_preorder(tree1)
print("Tree2 is: ")
print_preorder(tree2)
merged_tree=merge_two_binary_trees(tree1, tree2)
print("Merged Tree is: ")
print_preorder(merged_tree)