Convert a given tree to its Sum Tree | Node defintion ; Convert a given tree to a tree where every node contains sum of values of nodes in left and right subtrees in the original tree ; Base case ; Store the old value ; Recursively call for left and right subtrees and store the sum as new value of this node ; Return the sum of values of nodes in left and right subtrees and old_value of this node ; A utility function to print inorder traversal of a Binary Tree ; Utility function to create a new Binary Tree node ; Driver Code ; Constructing tree given in the above figure ; Print inorder traversal of the converted tree to test result of toSumTree ( )
class node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . left = None NEW_LINE self . right = None NEW_LINE self . data = data NEW_LINE DEDENT DEDENT def toSumTree ( Node ) : NEW_LINE INDENT if ( Node == None ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT old_val = Node . data NEW_LINE Node . data = toSumTree ( Node . left ) + toSumTree ( Node . right ) NEW_LINE return Node . data + old_val NEW_LINE DEDENT def printInorder ( Node ) : NEW_LINE INDENT if ( Node == None ) : NEW_LINE INDENT return NEW_LINE DEDENT printInorder ( Node . left ) NEW_LINE print ( Node . data , end = " ▁ " ) NEW_LINE printInorder ( Node . right ) NEW_LINE DEDENT def newNode ( data ) : NEW_LINE INDENT temp = node ( 0 ) NEW_LINE temp . data = data NEW_LINE temp . left = None NEW_LINE temp . right = None NEW_LINE return temp NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = None NEW_LINE x = 0 NEW_LINE root = newNode ( 10 ) NEW_LINE root . left = newNode ( - 2 ) NEW_LINE root . right = newNode ( 6 ) NEW_LINE root . left . left = newNode ( 8 ) NEW_LINE root . left . right = newNode ( - 4 ) NEW_LINE root . right . left = newNode ( 7 ) NEW_LINE root . right . right = newNode ( 5 ) NEW_LINE toSumTree ( root ) NEW_LINE print ( " Inorder ▁ Traversal ▁ of ▁ the ▁ resultant ▁ tree ▁ is : ▁ " ) NEW_LINE printInorder ( root ) NEW_LINE DEDENT