Binary Search Trees: Convert a BST into greater sum tree

Problem Statement:

You are given a root node of BST.

You need to convert into a greater sum tree.

Example

Input:
           4
          / \
         3   6

Output:
           6
          / \
         10   0

Solution

Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node.

For the solution, we need to work from biggest to smallest.

So we will have a temp variable “pre_val” what will store the previous value that we get, that is the total sum of bigger values.

For every node, update root->data with root->data + pre_val.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 

 int pre = 0;
 Node* BST_to_Gst(Node* root) 
 {
     if (root->right) BST_to_Gst(root->right);
     pre = root->data = pre + root->data;
     if (root->left) BST_to_Gst(root->left);
     return root;
 }

int main()
{
    Node *root_1 = NULL; 
    root_1 = insert_into_bst(root_1, 1); 
    insert_into_bst(root_1, 2); 
    insert_into_bst(root_1, 3); 
    insert_into_bst(root_1, 4); 
    insert_into_bst(root_1, 5); 

    cout<<"Inorder traversal is ";
    print_inorder(root_1);

    BST_to_Gst(root_1);

    cout<<"\nInorder traversal is after BST to GST";
    print_inorder(root_1);


    return 0;
}

Output:

Inorder traversal is 1 2 3 4 5
Inorder traversal is after BST to GST 15 14 12 9 5