12. Binary Search Tree to Greater Sum Tree / Greater 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 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 = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

Example 2:
Input: root = [0,null,1]
Output: [1,null,1]


Example 3:
Input: root = [1,0,2]
Output: [3,3,2]


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

Solution:

Bruteforce solution is using two traversal 1 traversing and 1 checking nodes which are greater O(n^2)

Solution I: (Using inorder traversal and sorted array)

Approach: Inorder Traversal gives sorted array Making prefix sum form right to left Again doing inorder traversal and inserting values

class Solution
{
public:
    TreeNode *bstToGst(TreeNode *root)
    {

        vector<int> v;

        stack<TreeNode *> s;
        TreeNode *t = root;
        while (!s.empty() || t != NULL)
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->left;
            }
            else
            {
                t = s.top();
                s.pop();
                v.push_back(t->val);
                t = t->right;
            }
        }

        for (int i = v.size() - 2; i >= 0; i--)
        {
            v[i] = v[i + 1] + v[i];
        }

        int i = 0;
        stack<TreeNode *> st;
        t = root;
        while (!st.empty() || t != NULL)
        {

            if (t != NULL)
            {
                st.push(t);
                t = t->left;
            }
            else
            {
                t = st.top();
                st.pop();
                t->val = v[i];
                i++;
                t = t->right;
            }
        }

        return root;
    }
};

Time Complexity: O(N) Space Complexity: O(n)

Solution II: (Reverse Inorder)

class Solution
{
public:
    TreeNode *convertBST(TreeNode *root)
    {

        TreeNode *t = root;

        stack<TreeNode *> s;
        int sum = 0;
        while (!s.empty() || t != NULL)
        {

            if (t != NULL)
            {
                s.push(t);
                t = t->right;
            }
            else
            {
                t = s.top();
                sum += t->val;
                t->val = sum;
                s.pop();
                t = t->left;
            }
        }
        return root;
    }
};

Time Complexity: O(N) Space Complexity: O(n)