Add all greater values to every node in a BST Python

PROGRAM TO ADD ALL GREATER VALUES TO EVERY NODE IN A GIVEN BST




class newNode: 

  

    # Constructor to create a new node 

    def __init__(self, data): 

        self.data = data 

        self.left = None

        self.right = None

  

# Recursive function to add all greater

# values in every node 

def modifyBSTUtil(root, Sum):

      

    # Base Case 

    if root == None:

        return

  

    # Recur for right subtree 

    modifyBSTUtil(root.right, Sum) 

  

    # Now Sum[0] has sum of nodes in right 

    # subtree, add root.data to sum and

    # update root.data 

    Sum[0] = Sum[0] + root.data 

    root.data = Sum[0]

  

    # Recur for left subtree 

    modifyBSTUtil(root.left, Sum)

  

# A wrapper over modifyBSTUtil() 

def modifyBST(root):

    Sum = [0]

    modifyBSTUtil(root, Sum)

  

# A utility function to do inorder

# traversal of BST 

def inorder(root):

    if root != None:

        inorder(root.left)

        print(root.data, end =" ") 

        inorder(root.right)

  

# A utility function to insert a new node 

# with given data in BST

def insert(node, data):

      

    # If the tree is empty, return a new node

    if node == None:

        return newNode(data)

  

    # Otherwise, recur down the tree

    if data <= node.data: 

        node.left = insert(node.left, data) 

    else:

        node.right = insert(node.right, data)

  

    # return the (unchanged) node pointer

    return node

  

# Driver Code

if __name__ == '__main__':

      

    # Let us create following BST 

    # 50 

    #     /     \ 

    # 30     70 

    #     / \ / \ 

    # 20 40 60 80

    root = None

    root = insert(root, 50) 

    insert(root, 30) 

    insert(root, 20) 

    insert(root, 40) 

    insert(root, 70) 

    insert(root, 60) 

    insert(root, 80) 

  

    modifyBST(root) 

  

    # print inoder tarversal of the

    # modified BST 

    inorder(root)




OUTPUT:

350 330 300 260 210 150 80

CREDITS: https://www.geeksforgeeks.org/add-greater-values-every-node-given-bst/