Question

Write a function in Python that adds two Binary Trees together. The inputs of your function should be two binary trees (or their roots, depending on how you plan on coding this), and the output will be one Binary Tree that is the sum of the two inputted.

• To add Binary Trees together: Add the values of nodes with the same position in both trees together, this will be the value assigned to the node of the same position in your output tree
• If one tree has a node that the other tree does not, the value of that node in the output tree will just simply be the same as it is in the initial tree
• Think about overlapping the trees and adding the nodes together that overlap
• You are to assume that all the trees being inputted will be Binary Trees (only points left and right)

Answer 1

Required Answer

# Required python program to add two given binary trees
class new_node: 
        def __init__(self, data): 
                self.data = data 
                self.left = self.right = None

# Given a binary tree, prints nodes in inorder_traversal 
#first recur the left node,then root node and then the right node
def inorder_traversal(node): 
        if (not node): 
                return
        inorder_traversal(node.left) 
        print(node.data, end = " ") 
        inorder_traversal(node.right) 

# Function to Add given two binary trees 
def Add_Trees(b_tree1, b_tree2): 
        if (not b_tree1): 
                return b_tree2 
        if (not b_tree2): 
                return b_tree1 
        b_tree1.data += b_tree2.data 
        b_tree1.left = Add_Trees(b_tree1.left, b_tree2.left) 
        b_tree1.right = Add_Trees(b_tree1.right, b_tree2.right) 
        return b_tree1 

# Driver code 
if __name__ == '__main__': 
        
    #creating the first binary tree
        tree1 = new_node(10) 
        tree1.left = new_node(20) 
        tree1.right = new_node(30) 
        tree1.left.left = new_node(40) 
        tree1.left.right = new_node(50) 
        tree1.right.right = new_node(60)
        tree1.right.right.right = new_node(100)

    #creating the second binary tree
        tree2 = new_node(40) 
        tree2.left = new_node(10) 
        tree2.right = new_node(70) 
        tree2.left.left = new_node(30) 
        tree2.right.left = new_node(20) 
        tree2.right.right = new_node(60)
        
        #Printing the first binary tree in inorder traversal
        print("The first binary tree is:")
        inorder_traversal(tree1)
        
        #Printing the second binary tree in inorder traversal
        print("\nThe second binary tree is:")
        inorder_traversal(tree2)
        
        #Calling the function two add the two trees
        final_tree = Add_Trees(tree1, tree2) 
        print("\nThe final Binary Tree is:") 
        inorder_traversal(final_tree) 

Screenshot of code and output: