Python program to merge two binary trees by doing node sum using recursion
Description:
To merge two binary trees using recursion, the rule is that if two nodes overlap, then sum nodes value up as the new value of the merged node. Otherwise , the non-null node will be used as the node of the new tree.
Example:
Input:
Tree 1 Tree 2
Output:
Merged Tree
So the algorithm for recursive approach is :
Traverse the tree in pre-order fashion.
Check if both the tree nodes are null, if not then update the value
Recur for left sub trees
Recur for right sub trees
Return root of updated tree
Program:
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# Given a binary tree, prits nodes in inorder
def inorder(node):
if (not node):
return
# first recur on left child
inorder(node.left)
# then print the data of node
print(node.data, end = " ")
# now recur on right child
inorder(node.right)
# Function to merge given twobinary trees
def MergeTrees(t1, t2):
if (not t1):
return t2
if (not t2):
return t1
t1.data += t2.data
t1.left = MergeTrees(t1.left, t2.left)
t1.right = MergeTrees(t1.right, t2.right)
return t1
# Driver code
if __name__ == '__main__':
# Let us construct the first Binary Tree
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root1 = newNode(1)
root1.left = newNode(2)
root1.right = newNode(3)
root1.left.left = newNode(4)
root1.left.right = newNode(5)
root1.right.right = newNode(6)
# Let us construct the second Binary Tree
# 4
# / \
# 1 7
# / / \
# 3 2 6
root2 = newNode(4)
root2.left = newNode(1)
root2.right = newNode(7)
root2.left.left = newNode(3)
root2.right.left = newNode(2)
root2.right.right = newNode(6)
root3 = MergeTrees(root1, root2)
print("The Merged Binary Tree is:")
inorder(root3)
Output:
The Merged Binary Tree is:
7 3 5 5 2 10 12
>>>
Comments