Binary Search Tree to Greater Sum Tree

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input: root = [3,2,4,1]
Output: [7,9,4,10]

Approach

Java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BSTtoGreaterSumTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.right = new TreeNode(4);
        root.left.left = new TreeNode(1);
        sum = 0;
        root = bstToGst(root);
        printTree(root);
    }

    static int sum = 0;

    static TreeNode bstToGst(TreeNode root) {
        if (root == null)
            return null;

        // call for right subtree
        bstToGst(root.right);

        // add current node into sum
        sum += root.val;

        // uodate root data
        root.val = sum;

        // call for left subtree
        bstToGst(root.left);
        return root;
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode
{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int sum = 0;
TreeNode *bstToGst(TreeNode *root)
{
    if (root == NULL)
        return NULL;

    //call for right subtree
    bstToGst(root->right);

    //add current node into sum
    sum += root->data;

    //uodate root data
    root->data = sum;

    //call for left subtree
    bstToGst(root->left);
    return root;
}

//function to print the tree
void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
            vec.push_back("null");
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
     int j=vec.size()-1;
     while(j>0&&vec[j]=="null")
        j--;
      vec.resize(j);
      for(int i=0;i<j;i++)
        cout<<vec[i]<<",";
      cout<<vec[j];
}
int main()
{
    //[3,2,4,1]
    TreeNode *root=new TreeNode(3);
    root->left=new TreeNode(2);
    root->right=new TreeNode(4);
    root->left->left=new TreeNode(1);

    root=bstToGst(root);

    printTree(root);

}