Binary Search Tree to Greater Sum Tree

class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        int totalSum = 0;
        TreeNode* current = root;

        while (current != nullptr) {
            if (current->right == nullptr) {
                totalSum += current->val;
                current->val = totalSum;
                current = current->left;
            } else {
                TreeNode* successor = findSuccessor(current);
                if (successor->left == nullptr) {
                    successor->left = current;
                    current = current->right;
                } else {
                    successor->left = nullptr;
                    totalSum += current->val;
                    current->val = totalSum;
                    current = current->left;
                }
            }
        }

        return root;
    }

private:
    TreeNode* findSuccessor(TreeNode* node) {
        TreeNode* currentSuccessor = node->right;
        while (currentSuccessor->left != nullptr && currentSuccessor->left != node) {
            currentSuccessor = currentSuccessor->left;
        }
        return currentSuccessor;
    }
};

Transform a Binary Search Tree (BST) into a Greater Sum Tree using a C++ implementation, where each node's value is updated to the sum of all values greater than itself. The approach utilizes a reversed in-order traversal to accumulate values from greatest to least, leveraging the tree's right skew to facilitate the process. Here's a high-level summary:

1. Start by initializing totalSum to 0, which will keep track of the running total of node values when traversed from the largest to the smallest.
2. Use a pointer current to traverse the tree. Begin at the root node.
3. While traversing, focus on processing the right child first since it contains the larger values. For each node:
   • If the node lacks a right child, directly add its value to totalSum, update the node's value to totalSum, and proceed to the left child.
   • If a right child exists, find the inorder successor—the smallest node of the right subtree—and properly adjust the tree structure for seamless traversal.
4. The findSuccessor function aids in locating an inorder successor by navigating to the leftmost node of the right subtree.
5. Repeat the while loop until all nodes are processed. Each node's value is swapped with totalSum, and traversal continues to cover all nodes.

This approach amends each node's value in the BST to reflect the sum of nodes with greater values, efficiently converting the BST into a Greater Sum Tree and preserving the structural integrity of the original tree. This process efficiently works in-place, providing an optimal solution without using auxiliary space for additional data structures beyond the recursive stack during the successor finding.

class Solution {

    public TreeNode convertBstToGst(TreeNode root) {
        int total = 0;
        TreeNode current = root;

        while (current != null) {
            if (current.right == null) {
                total += current.val;
                current.val = total;
                current = current.left;
            } else {
                TreeNode successor = findSuccessor(current);
                if (successor.left == null) {
                    successor.left = current;
                    current = current.right;
                } else {
                    successor.left = null;
                    total += current.val;
                    current.val = total;
                    current = current.left;
                }
            }
        }

        return root;
    }

    private TreeNode findSuccessor(TreeNode node) {
        TreeNode nextNode = node.right;
        while (nextNode.left != null && nextNode.left != node) {
            nextNode = nextNode.left;
        }
        return nextNode;
    }
}

This solution provides an implementation for transforming a Binary Search Tree (BST) into a Greater Sum Tree (GST) using Java. In a GST, each node contains the original value plus the sum of all nodes greater than it in the BST. The approach follows these key steps:

1. Initialize a variable total to keep the cumulative sum and set a current pointer to the root.
2. Use a while loop to traverse the tree. Within the loop:
   • Check if the current node’s right child is null. If true, add its value to total, update the current value to total, and move to the left child.
   • If the right child exists, find the inorder successor, which is the smallest node in the right subtree:
     • If the successor has no left child, link the current node as a left child to the successor and move current to its right child.
     • If the successor's left child is the current node, remove this link, update current node's value with total, and move to the left child.
3. Continue the iteration until current becomes null.
4. The tree is modified in-place and the method returns the modified tree root.

In this algorithm, the recursive function findSuccessor is key for maintaining the structure of the GST:

• It starts with the right child of the given node and traverses left until it finds the appropriate successor node or until it circles back to the original node.

This efficient control structure and traversal method ensure that each node is processed in descending order (right to left), which is essential for the correct accumulation of sums for the GST transformation. The technique avoids the need for additional storage structures and performs updates in a single pass, leveraging the properties of the BST.

class Solution(object):
    def treeToGst(self, root):
        # Helper to find the in-order successor in a BST
        def find_successor(node):
            next_node = node.right
            while next_node.left is not None and next_node.left is not node:
                next_node = next_node.left
            return next_node

        accumulated_sum = 0
        current_node = root
        while current_node is not None:
            if current_node.right is None:
                accumulated_sum += current_node.val
                current_node.val = accumulated_sum
                current_node = current_node.left
            else:
                successor = find_successor(current_node)
                if successor.left is None:
                    successor.left = current_node
                    current_node = current_node.right
                else:
                    successor.left = None
                    accumulated_sum += current_node.val
                    current_node.val = accumulated_sum
                    current_node = current_node.left

        return root

The provided Python 3 code is designed to transform a Binary Search Tree (BST) into a Greater Sum Tree (GST). Each node's value in the new tree is replaced by the sum of all values greater than or equal to that node's value in the original BST. This transformation is done in-place.

Here is a breakdown of the algorithm:

• Define a helper function find_successor to locate the in-order successor of a node. For a given node, the successor is the leftmost node in its right subtree.

• Initialize accumulated_sum to store the rolling sum of node values as they are visited in reverse in-order (right-to-left).

• Traverse the tree starting from the root:

  • If the current_node does not have a right child, add the node's value to accumulated_sum, update the node's value with accumulated_sum, and move to the left child.
  • If the current_node has a right child, find the in-order successor. If this successor node does not have a left child, link the current node to this successor, and proceed to the right child of the current node. Otherwise, unlink the current node from the successor, update the current_node's value with accumulated_sum after adding its own value, and move to the left child.

• Continue the traversal until all nodes are processed. Then, return the root of the transformed tree.

Ensure every step respects the properties of BSTs, to maintain the structural integrity while converting it into a GST. The solution modifies the input BST directly, making the transformation efficient in terms of memory usage, as it obviates the need for additional storage for another tree.