 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
>>> More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 629 20
Tokenize text using NLTK in Python. 1074 12
Python Remove multiple elements from list while Iterating. 673 22
Python How to Check if an item exists in list ? 4004 14
Python How to remove multiple elements from list ? 645 26
Python program to check if two trees are mirror of each other without using recursion. 593 19
Python program to find maximum in Binary tree. 802 19
Python Check if all elements are same using Set 616 15
Python program to find diameter of a binary tree. 960 20
Python program to print root to leaf paths without using recursion. 733 20
Python program to find root of the tree where children id sum for every node is given. 578 23
Introduction of Python NLTK library 1211 25
Categorizing and Tagging Sentences using NLTK in Python . 858 19
Python program to find height of a tree without using recursion. 594 16
Python program to find sum of all nodes of the given perfect binary tree. 586 19
Python program to find minimum in binary tree. 689 23
Python Check if element exist in list using list.count() function. 624 13
Python program to convert a given binary tree to doubly linked list. 792 20
Python program to find distance between two nodes of a binary tree. 1356 20
NLTK stop Words 955 13
Python program to find largest binary search tree in a Binary Tree. 828 20
Python program to find inorder successor in binary search tree with recursion. 1023 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 612 15
Python List check if element are same using all() 590 12
Python program to check if two trees are identical using recursion. 639 30
Python Find the occurrence count of an element in the tuple using count() 883 23
Python Convert two lists to a dictionary 637 19
Python program to construct a complete binary tree from given array. 1158 14
Python program to find diameter of binary tree in O(n). 762 17
Introduction to the AVL tree. 635 15
Python program to check if two trees are identical without using recursion 602 17
Python Convert a list of tuples to dictionary. 908 24
Python program to convert a binary tree to a circular doubly link list. 584 21
Python Check if element exist in list based on own logic. 681 23
Python program to merge two binary trees by doing node sum using recursion 916 27
Python program to check whether a given binary tree is perfect or not. 604 17
Python Check if all elements are same using list.count(). 958 28
Python program to find an element into binary tree 555 12
Python program to find lowest common ancestor in a binary tree 1080 24