Python program to convert a given tree to its Sumtree

Description :
Given Tree where each node has positive and negative values. Convert this to a sum tree
which means tree where each node contains the sum of the left and right sub trees in the original tree
and values of leaf nodes became 0.

Example: Inserted tree is
20
/ \
4-2
/ \ / \
8-475
when we convert the given tree to sum tree it looks like:
18 (8-4+7+5+4-2) # sum of all subtree nodes
/ \
(8-4) 412(7+5)
/ / \
0000

Program:import time
#Return the current time in seconds since the Epoch.#Fractions of a second may be present if the system clock provides them.#start time
start=time.time()
classNode:# Constructor to create a new node def__init__(self, key):
self.node = key
self.left = None
self.right = NoneclassSumTree:deftoSumTree( self,root):# Base case if root isNone:
return0# Store the old value
old_val = root.node
# Recursively call for left and right subtrees and store the sum as # new value of this node
root.node=self.toSumTree(root.left) + self.toSumTree(root.right)
# Return the sum of values of nodes in left and right subtrees and # old_value of this node return root.node + old_val
deftraverse_inorder(self,root):if root==None:
return
self.traverse_inorder(root.left)
print(root.node,end=" ")
self.traverse_inorder(root.right)
defmain():
st=SumTree()
root = Node(20)
root.left = Node(4)
root.right = Node(-2)
root.left.left = Node(8)
root.left.right = Node(-4)
root.right.left = Node(7)
root.right.right = Node(5)
print("Binary Tree which is Inserted:")
st.traverse_inorder(root)
st.toSumTree(root)
print("\nsum tree :")
st.traverse_inorder(root)
if __name__ == "__main__":
main()
# end time
end=time.time()
print("\nExecution Time is {}".format(end-start),"seconds")
Output:
Binary Tree which is Inserted:
84-4207-25
sum tree :
040180120
Execution Time is0.0790557861328125 seconds

## Comments