# Add all greater values to every node in a given BST

Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node. For example, consider the following BST.

```              50
/
30        70
/         /
20    40    60   80

The above tree should be modified to following

260
/
330        150
/          /
350   300    210   80```

A simple method for solving this is to find sum of all greater values for every node. This method would take O(n^2) time.
We can do it using a single traversal. The idea is to use following BST property. If we do reverse Inorder traversal of BST, we get all nodes in decreasing order. We do reverse Inorder traversal and keep track of the sum of all nodes visited so far, we add this sum to every node.

## C

 `// C program to add all greater values in every node of BST ` `#include ` `#include ` ` `  `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node *left, *right; ` `}; ` ` `  `// A utility function to create a new BST node ` `struct` `Node *newNode(``int` `item) ` `{ ` `    ``struct` `Node *temp =  (``struct` `Node *)``malloc``(``sizeof``(``struct` `Node)); ` `    ``temp->data = item; ` `    ``temp->left = temp->right = NULL; ` `    ``return` `temp; ` `} ` ` `  `// Recursive function to add all greater values in every node ` `void` `modifyBSTUtil(``struct` `Node *root, ``int` `*sum) ` `{ ` `    ``// Base Case ` `    ``if` `(root == NULL)  ``return``; ` ` `  `    ``// Recur for right subtree ` `    ``modifyBSTUtil(root->right, sum); ` ` `  `    ``// Now *sum has sum of nodes in right subtree, add ` `    ``// root->data to sum and update root->data ` `    ``*sum = *sum + root->data; ` `    ``root->data = *sum; ` ` `  `    ``// Recur for left subtree ` `    ``modifyBSTUtil(root->left, sum); ` `} ` ` `  `// A wrapper over modifyBSTUtil() ` `void` `modifyBST(``struct` `Node *root) ` `{ ` `    ``int` `sum = 0; ` `    ``modifyBSTUtil(root, &sum); ` `} ` ` `  `// A utility function to do inorder traversal of BST ` `void` `inorder(``struct` `Node *root) ` `{ ` `    ``if` `(root != NULL) ` `    ``{ ` `        ``inorder(root->left); ` `        ``printf``(``"%d "``, root->data); ` `        ``inorder(root->right); ` `    ``} ` `} ` ` `  `/* A utility function to insert a new node with given data in BST */` `struct` `Node* insert(``struct` `Node* node, ``int` `data) ` `{ ` `    ``/* If the tree is empty, return a new node */` `    ``if` `(node == NULL) ``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 Program to test above functions ` `int` `main() ` `{ ` `    ``/* Let us create following BST ` `              ``50 ` `           ``/     ` `          ``30      70 ` `         ``/      /  ` `       ``20   40  60   80 */` `    ``struct` `Node *root = NULL; ` `    ``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); ` ` `  `    ``return` `0; ` `}`

## Java

 `// Java code to add all greater values to  ` `// every node in a given BST ` ` `  `// A binary tree node ` `class` `Node { ` ` `  `    ``int` `data; ` `    ``Node left, right; ` ` `  `    ``Node(``int` `d) ` `    ``{ ` `        ``data = d; ` `        ``left = right = ``null``; ` `    ``} ` `} ` ` `  `class` `BinarySearchTree { ` ` `  `    ``// Root of BST ` `    ``Node root; ` ` `  `    ``// Constructor ` `    ``BinarySearchTree() ` `    ``{ ` `        ``root = ``null``; ` `    ``} ` ` `  `    ``// Inorder traversal of the tree ` `    ``void` `inorder() ` `    ``{ ` `        ``inorderUtil(``this``.root); ` `    ``} ` ` `  `    ``// Utility function for inorder traversal of ` `    ``// the tree ` `    ``void` `inorderUtil(Node node) ` `    ``{ ` `        ``if` `(node == ``null``) ` `            ``return``; ` ` `  `        ``inorderUtil(node.left); ` `        ``System.out.print(node.data + ``" "``); ` `        ``inorderUtil(node.right); ` `    ``} ` ` `  `    ``// adding new node  ` `    ``public` `void` `insert(``int` `data) ` `    ``{ ` `        ``this``.root = ``this``.insertRec(``this``.root, data); ` `    ``} ` `     `  `    ``/* A utility function to insert a new node with  ` `    ``given data in BST */` `    ``Node insertRec(Node node, ``int` `data) ` `    ``{    ` `        ``/* If the tree is empty, return a new node */` `        ``if` `(node == ``null``) { ` `            ``this``.root = ``new` `Node(data); ` `            ``return` `this``.root; ` `        ``} ` ` `  `        ``/* Otherwise, recur down the tree */` `        ``if` `(data <= node.data) { ` `            ``node.left = ``this``.insertRec(node.left, data); ` `        ``} ``else` `{ ` `            ``node.right = ``this``.insertRec(node.right, data); ` `        ``} ` `        ``return` `node; ` `    ``} ` ` `  `    ``// This class initialises the value of sum to 0 ` `    ``public` `class` `Sum { ` `        ``int` `sum = ``0``; ` `    ``} ` ` `  `    ``// Recursive function to add all greater values in ` `    ``// every node ` `    ``void` `modifyBSTUtil(Node node, Sum S) ` `    ``{ ` `        ``// Base Case ` `        ``if` `(node == ``null``) ` `            ``return``; ` `             `  `        ``// Recur for right subtree     ` `        ``this``.modifyBSTUtil(node.right, S);  ` `         `  `        ``// Now *sum has sum of nodes in right subtree, add ` `        ``// root->data to sum and update root->data ` `        ``S.sum = S.sum + node.data; ` `        ``node.data = S.sum; ` `         `  `        ``// Recur for left subtree ` `        ``this``.modifyBSTUtil(node.left, S);  ` `    ``} ` ` `  `    ``// A wrapper over modifyBSTUtil() ` `    ``void` `modifyBST(Node node) ` `    ``{ ` `        ``Sum S = ``new` `Sum(); ` `        ``this``.modifyBSTUtil(node, S); ` `    ``} ` ` `  `    ``// Driver Function ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``BinarySearchTree tree = ``new` `BinarySearchTree(); ` `         `  `          ``/* Let us create following BST ` `              ``50 ` `           ``/     ` `          ``30      70 ` `         ``/      /  ` `       ``20   40  60   80 */` `        `  `        ``tree.insert(``50``); ` `        ``tree.insert(``30``); ` `        ``tree.insert(``20``); ` `        ``tree.insert(``40``); ` `        ``tree.insert(``70``); ` `        ``tree.insert(``60``); ` `        ``tree.insert(``80``); ` ` `  `        ``tree.modifyBST(tree.root); ` `         `  `        ``// print inoder tarversal of the modified BST ` `        ``tree.inorder(); ` `    ``} ` `} ` ` `  `// This code is contributed by Kamal Rawal `

## Python3

 `# Python3 program to add all greater values  ` `# in every node of BST  ` ` `  `# A utility function to create a ` `# new BST node  ` `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) ` `     `  `# This code is contributed by PranchalK `

## C#

 `using` `System; ` ` `  `// C# code to add all greater values to   ` `// every node in a given BST  ` ` `  `// A binary tree node  ` `public` `class` `Node ` `{ ` ` `  `    ``public` `int` `data; ` `    ``public` `Node left, right; ` ` `  `    ``public` `Node(``int` `d) ` `    ``{ ` `        ``data = d; ` `        ``left = right = ``null``; ` `    ``} ` `} ` ` `  `public` `class` `BinarySearchTree ` `{ ` ` `  `    ``// Root of BST  ` `    ``public` `Node root; ` ` `  `    ``// Constructor  ` `    ``public` `BinarySearchTree() ` `    ``{ ` `        ``root = ``null``; ` `    ``} ` ` `  `    ``// Inorder traversal of the tree  ` `    ``public` `virtual` `void` `inorder() ` `    ``{ ` `        ``inorderUtil(``this``.root); ` `    ``} ` ` `  `    ``// Utility function for inorder traversal of  ` `    ``// the tree  ` `    ``public` `virtual` `void` `inorderUtil(Node node) ` `    ``{ ` `        ``if` `(node == ``null``) ` `        ``{ ` `            ``return``; ` `        ``} ` ` `  `        ``inorderUtil(node.left); ` `        ``Console.Write(node.data + ``" "``); ` `        ``inorderUtil(node.right); ` `    ``} ` ` `  `    ``// adding new node   ` `    ``public` `virtual` `void` `insert(``int` `data) ` `    ``{ ` `        ``this``.root = ``this``.insertRec(``this``.root, data); ` `    ``} ` ` `  `    ``/* A utility function to insert a new node with   ` `    ``given data in BST */` `    ``public` `virtual` `Node insertRec(Node node, ``int` `data) ` `    ``{ ` `        ``/* If the tree is empty, return a new node */` `        ``if` `(node == ``null``) ` `        ``{ ` `            ``this``.root = ``new` `Node(data); ` `            ``return` `this``.root; ` `        ``} ` ` `  `        ``/* Otherwise, recur down the tree */` `        ``if` `(data <= node.data) ` `        ``{ ` `            ``node.left = ``this``.insertRec(node.left, data); ` `        ``} ` `        ``else` `        ``{ ` `            ``node.right = ``this``.insertRec(node.right, data); ` `        ``} ` `        ``return` `node; ` `    ``} ` ` `  `    ``// This class initialises the value of sum to 0  ` `    ``public` `class` `Sum ` `    ``{ ` `        ``private` `readonly` `BinarySearchTree outerInstance; ` ` `  `        ``public` `Sum(BinarySearchTree outerInstance) ` `        ``{ ` `            ``this``.outerInstance = outerInstance; ` `        ``} ` ` `  `        ``public` `int` `sum = 0; ` `    ``} ` ` `  `    ``// Recursive function to add all greater values in  ` `    ``// every node  ` `    ``public` `virtual` `void` `modifyBSTUtil(Node node, Sum S) ` `    ``{ ` `        ``// Base Case  ` `        ``if` `(node == ``null``) ` `        ``{ ` `            ``return``; ` `        ``} ` ` `  `        ``// Recur for right subtree      ` `        ``this``.modifyBSTUtil(node.right, S); ` ` `  `        ``// Now *sum has sum of nodes in right subtree, add  ` `        ``// root->data to sum and update root->data  ` `        ``S.sum = S.sum + node.data; ` `        ``node.data = S.sum; ` ` `  `        ``// Recur for left subtree  ` `        ``this``.modifyBSTUtil(node.left, S); ` `    ``} ` ` `  `    ``// A wrapper over modifyBSTUtil()  ` `    ``public` `virtual` `void` `modifyBST(Node node) ` `    ``{ ` `        ``Sum S = ``new` `Sum(``this``); ` `        ``this``.modifyBSTUtil(node, S); ` `    ``} ` ` `  `    ``// Driver Function  ` `    ``public` `static` `void` `Main(``string``[] args) ` `    ``{ ` `        ``BinarySearchTree tree = ``new` `BinarySearchTree(); ` ` `  `          ``/* Let us create following BST  ` `              ``50  ` `           ``/       ` `          ``30      70  ` `         ``/      /    ` `       ``20   40  60   80 */` ` `  `        ``tree.insert(50); ` `        ``tree.insert(30); ` `        ``tree.insert(20); ` `        ``tree.insert(40); ` `        ``tree.insert(70); ` `        ``tree.insert(60); ` `        ``tree.insert(80); ` ` `  `        ``tree.modifyBST(tree.root); ` ` `  `        ``// print inoder tarversal of the modified BST  ` `        ``tree.inorder(); ` `    ``} ` `} ` ` `  `  ``// This code is contributed by Shrikant13 `

Output

`350 330 300 260 210 150 80`

Time Complexity: O(n) where n is number of nodes in the given BST.

As a side note, we can also use reverse Inorder traversal to find kth largest element in a BST.