Add all greater values to every node in a given BST

Approach

🔺In the given problem to Add all greater values to every node in a given BST, we will use the reverse in order traversal to solve it in a single traversal.

🔺We can see that the largest node remains constant. The value of the second largest node equals the sum of the values of the first and second largest nodes.

🔺Similarly, the value of the nth largest node after modification will be the sum of the n-th node and the value of the (n-1)the largest node.

🔺 So, we may solve the problem by traversing the tree in descending order and updating the sum value at each step while adding the value to the root node.

🔺So we utilize reverse in-order BST traversal to traverse the BST in decreasing order. 

🔺Then we take a global variable sum, which we update at each node, and when it reaches the root node, we will replace the variable sum value with the root node's value, which is updated.

Algorithm 

🔻 To solve this problem, we have created three functions first is to insert the nodes in a binary search tree, second is for inorder traversal, and the third is for modifying the tree with the greater values.

🔻The insertion function has two arguments one is to determine the child of the tree and the other is the value, in-order traversal function has one argument on which we will perform the traversal.

🔻The third function has two arguments one is root and the other is a sum that calculates the greater value.

🔻  We are inserting the data by the following method:

if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

🔻 Finally, we will print the nodes of the binary search tree with greater values.

C++ code

// C++ program to add all greater values in binary Search Tree at each node
#include <bits/stdc++.h>
using namespace std;

class Node
{
public:
    int data;
    Node *left, *right;
};

// A function to create a new BST node to find greater values in binary search
// tree
Node *newNode(int item)
{
    Node *temporary = new Node();
    temporary->data = item;
    temporary->left = temporary->right = NULL;
    return temporary;
}

// Recursive function to add all greater values in binary search tree in  every
// node
void modifyingBST(Node *root, int *sum)
{
    // Base Case
    if (root == NULL)
        return;

    // Recur for right subtree
    modifyingBST(root->right, sum);

    // Now *sum has sum of nodes
    // in right subtree,
    *sum = *sum + root->data;
    root->data = *sum;

    // Recursion for left subtree
    modifyingBST(root->left, sum);
}

void inordertraversal(Node *root)
{
    if (root != NULL)
    {
        inordertraversal(root->left);
        cout << root->data << " ";
        inordertraversal(root->right);
    }
}

// A function to insert a new node with given data in BST
Node *insertion(Node *node, int data)
{
    /* If the tree is empty,
    return a new node */
    if (node == NULL)
        return newNode(data);

    if (data <= node->data)
        node->left = insertion(node->left, data);
    else
        node->right = insertion(node->right, data);

    /* return the  node pointer */
    return node;
}

// Driver code to find greater values in binary search tree at each node
int main()
{

    Node *root = NULL;
    int n1;
    int arr[4];
    int size;

    cout << "\n enter the root node value ";
    cin >> n1;

    root = insertion(root, n1);
    cout << "enter the number of nodes which you want to insert in the tree ";
    cin >> size;
    cout << "enter the nodes of the tree ";
    for (int i = 0; i < size; i++)
    {
        cin >> arr[i];
        insertion(root, arr[i]);
    }

    int sum = 0;
    // adding greater values in binary search tree at each node
    modifyingBST(root, &sum);
    // print inordertraversal traversal of the modified BST
    inordertraversal(root);

    return 0;
}

Output 

Complexity analysis

Time complexity

O(N), where N is the number of nodes in the tree. This is because we are using one loop to traverse the tree in reverse traversal.

Space complexity

O(N), where N is the number of nodes in the tree. This is because we are using an array to take the data from the user for each node.

Check out this problem - Reverse Nodes In K Group

Frequently Asked Questions

What is a tree data structure?

A tree is a non-linear, hierarchical data structure comprised of several nodes containing a value and a list of links to other nodes (referred to as "children"). This data structure is a way to set up data storage and organization in the computer so tree data structure can use more efficiently.

What distinguishes a binary search tree from a binary tree in particular?

A binary tree version that arranges the nodes in a certain order is known as a binary search tree. With the straightforward limitation that no parent can have more than two offspring, a binary tree is a fundamental structure.

What is a red-black tree?

The characteristics of the Red-Black tree, a unique variety of self-balancing tree, include:

1. Red or black are the two colors that each node can have.
2. Always black is the root node.
3. There can't be a red parent or red child for a red node.
4. The number of black nodes is the same.

Conclusion

In this article, we have briefly discussed the binary search tree data structure, examples, approach, and how to Add all greater values to every node in a given BST, time, and space complexity with O(N) time and space complexities.

After reading about how to print the largest add all greater values to every node in a given BST, are you not feeling excited to read/explore more articles on the topic of file systems? Don't worry; Coding Ninjas has you covered. If you want to practice questions on the binary tree then follow these links: Insertion in BST, Symmetric tree, BST to sorted DLL, Preorder binary tree, Range Sum of BST, Sum of all nodes with smaller values at a distance ‘K’ from the given node in BST, and Preorder traversal.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!