Python program to convert a given tree to its Sumtree














































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 -4 7 5 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) 4 12(7+5) / / \ 0 0 0 0
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() class Node: # Constructor to create a new node def __init__(self, key): self.node = key self.left = None self.right = None class SumTree: def toSumTree( self,root): # Base case if root is None: return 0 # 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 def traverse_inorder(self,root): if root==None: return self.traverse_inorder(root.left) print(root.node,end=" ") self.traverse_inorder(root.right) def main(): 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: 8 4 -4 20 7 -2 5 sum tree : 0 4 0 18 0 12 0 Execution Time is 0.0790557861328125 seconds

Thank you happy coding :)

More Articles of Akrati Sharma:

Name Views Likes
Python numpy program to generate random number 834 0
Program to construct BST from level order traversal 643 2
Python numpy program to find sum the diagonal elements of the matrix 8457 1
Python find sum the diagonal elements of the matrix 1605 0
python numpy find the transpose of a matrix 393 0
Python numpy convert a csv file date to a matrix 492 1
Python program to read configuration file 382 1
Python program to convert doc file into pdf file. 997 19
Python program to add new page at the end of a pdf file 310 18
Python Program to find sink odd nodes in binary tree. 436 14
creating project in pythons scrapy library 405 16
Python program to check given array of size n can represent binary search tree of n levels or not. 298 16
Python program to find out greater sum tree elements of binary search tree 306 17
Selectors of scrapy library 396 24
Introduction to python scrapy library 314 16
Python Program to find an element in tuple by value using in and not in 288 18
Find an element in tuple by value using in and not in : 93 25
Python program to count Half Nodes in Binary Tree recursion 443 20
Python Program to find top three elements in binary tree. 262 20
Python program to count half nodes in binary tree without recursion 374 14
Python program to find deepest right leaf node in a binary tree using recursion. 350 18
Python program to convert a given tree to its Sumtree 490 26
Python program to convert a tree into its sum tree 84 21
Python Program to Convert Binary tree into Binary Search Tree 381 17
Python Program to check if each internal node of a BST has exactly one child 334 18
Python Program to find median of binary search tree 637 11
Python Program to find an Element into a Binary tree. 261 18
Python program to replace every element with the least greater element on its right 326 18
Python Program to delete an element at specific index in tuple. 20 13
Python program to insert an element to specific position in tuple 361 20
Python program to insert an element at specific position in tuple. 13 11
Python Program to append an element in tuple at the end. 313 20
Python Program to count subtree that sum up to a given value x 558 20
Python program to print all root to leaf paths with there relative positions 312 16
Python program to check given tree is Sumtree or not 412 16
Python program to find sum of nodes at maximum depth of a binary tree 505 21
Python Program to replace an element at specific index in tuple. 354 24
Python program to find given key x in binary tree 289 14
Python program to find vertical width of binary tree 352 15
Python program to find mirror of a given node in binary tree 369 19
Python program to find largest subtree sum in a tree 260 18
Python Program to calculate the size of tree without recursion 328 19
Python Program to find tilt of binary tree 452 18
Python Program to find maximum node in left subtree in binay tree. 240 16
Python program to convert a List to Dictionary with same Value. 278 19
Python program to count minimum swap require to construct Binary Search Tree from Binary tree 461 18
Program to construct BST from level order traversal 354 24
Python Program to delete an element at specific index in tuple. 572 21
Python Program to print all the elements in Binary Search tree. 1324 14

Comments