Recall the properties of a BST:

• 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 Scenarios

Input: [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]

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

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• 0 <= Node.val <= 100
• All values in the tree are unique.

Approach 1: Recursive Reverse Inorder Traversal

A standard inorder traversal of a BST visits nodes in ascending order. Conversely, a reverse inorder traversal (Right → Node → Left) visits nodes in descending order. By traversing in this manner, we can maintain a running cumulative sum. As we visit each node, we add its value to the running sum and update the node's value with this sum.

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int currentSum = 0;
        reverseInorder(root, currentSum);
        return root;
    }

private:
    void reverseInorder(TreeNode* node, int& currentSum) {
        if (!node) return;

        // Visit right subtree first (larger values)
        reverseInorder(node->right, currentSum);

        // Update running sum and node value
        currentSum += node->val;
        node->val = currentSum;

        // Visit left subtree (smaller values)
        reverseInorder(node->left, currentSum);
    }
};

Complexity Analysis:
Time Compleixty: O(n) - each node is visited exactly once.
Space Complexity: O(h) - where h is the height of the tree (O(log n) on average, O(n) in the worst case due to recurtion stack).

Approach 2: Iterative Stack-Based Traversal

To avoid recursion and potential stack overflow on very deep trees, we can use an explicit stack to simulate the reverse inorder traversal. The logic remains the same: process the rightmost node, then the current nodde, then move to the left.

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        std::stack<TreeNode*> nodeStack;
        int runningTotal = 0;
        TreeNode* curr = root;

        while (curr || !nodeStack.empty()) {
            // Traverse to the rightmost node
            while (curr) {
                nodeStack.push(curr);
                curr = curr->right;
            }

            // Process the current node
            curr = nodeStack.top();
            nodeStack.pop();

            runningTotal += curr->val;
            curr->val = runningTotal;

            // Move to the left subtree
            curr = curr->left;
        }

        return root;
    }
};

Complexity Analysis:
Time Complexity: O(n)
Space Complexity: O(h) - space required for the stack.

Approach 3: Morris Traversal for O(1) Space

We can optimize space complexity to O(1) using Morris Traversal. This approach modifies the tree structure temporarily by creating "threads" (links) from the predecessor back to the current node. For reverse inorder, the predecessor of a node is the leftmost node in its right subtree. We use these pointers to navigate back up without a stack.

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int accumulation = 0;
        TreeNode* curr = root;

        while (curr) {
            if (!curr->right) {
                // No right child, process current node
                accumulation += curr->val;
                curr->val = accumulation;
                curr = curr->left;
            } else {
                // Find the leftmost node in the right subtree (predecessor)
                TreeNode* predecessor = curr->right;
                while (predecessor->left && predecessor->left != curr) {
                    predecessor = predecessor->left;
                }

                if (!predecessor->left) {
                    // Create a temporary thread back to current
                    predecessor->left = curr;
                    curr = curr->right;
                } else {
                    // Thread exists, meaning we have returned to the node
                    predecessor->left = nullptr; // Break the thread
                    accumulation += curr->val;
                    curr->val = accumulation;
                    curr = curr->left;
                }
            }
        }
        return root;
    }
};

Complexity Analysis:
Time Complexity: O(n) - each edge is traversed a limited number of times.
Space Complexity: O(1) - no recursion stack or auxiliary storage used.

Approach 4: Repeated Predecessor Search

This method leverages the BST properties but is less efficient. We start by finding the absolute maximum value in the tree. Then, we iteratively search for the immediate predecessor (the largest value smaller than the current one). We accumulate the sum as we find each node.

class Solution {
public:
    TreeNode* bstToGst(TreeNode* root) {
        int sum = 0;
        // Start with the maximum value node
        TreeNode* current = findMaximum(root);
        
        while (current) {
            int lastVal = current->val;
            sum += current->val;
            current->val = sum;
            
            // Find the next largest value smaller than lastVal
            current = findPredecessor(root, lastVal);
        }
        return root;
    }

private:
    TreeNode* findMaximum(TreeNode* node) {
        while (node->right) {
            node = node->right;
        }
        return node;
    }

    TreeNode* findPredecessor(TreeNode* root, int target) {
        TreeNode* result = nullptr;
        while (root) {
            if (root->val > target) {
                root = root->left;
            } else if (root->val < target) {
                // Update result if we find a closer smaller value
                if (!result || root->val > result->val) {
                    result = root;
                }
                root = root->right;
            } else {
                break; // Found the target itself
            }
        }
        return result;
    }
};

Complexity Analysis:
Time Complexity: O(n log n) - finding the predecessor takes O(h) per node, repeated n times.
Space Complexity: O(1).