Binary Search Tree to Greater Sum Tree

To solve this coding challenge, you need to convert a given Binary Search Tree (BST) into a Greater Tree where each node's value is updated to be itself plus the sum of all values greater than it in the BST. The solution involves a depth-first search (DFS) traversal, specifically a reverse in-order traversal (right node, current node, left node), to accumulate the sum of nodes' values in a descending order. Here's how you can solve it along with the pseudo code:

Step 1: Initialize a Variable

Initialize a variable, say lastSum, to store the cumulative sum of node values encountered during the traversal. Start with lastSum set to 0.

Step 2: Define a Recursive DFS Function

Define a recursive function, say convertToGreaterTree(node), which will perform the reverse in-order traversal and update each node's value.

Step 3: Reverse In-Order Traversal

If the current node (node) is null, return immediately, as there's nothing to process. Recursively call convertToGreaterTree(node.right) to start traversal from the rightmost node (the largest value in a BST). Add lastSum to the current node's value (node.val) and update lastSum to be the new value of node.val. This step ensures that each node's value is updated to include the sum of all greater values in the tree. Recursively call convertToGreaterTree(node.left) to process the left subtree, which contains smaller values.

Step 4: Initiate the Traversal

Call convertToGreaterTree(root) with the root of the BST to start the conversion process.

Step 5: Return the Modified Tree

After the recursive function has updated all nodes, return the root of the modified tree.

Pseudo Code:

                                        
Function bstToGst(root)
    Initialize lastSum to 0

    Function convertToGreaterTree(node)
        If node is null, return

        // Traverse the right subtree
        convertToGreaterTree(node.right)

        // Update the current node's value and lastSum
        node.val = node.val + lastSum
        lastSum = node.val

        // Traverse the left subtree
        convertToGreaterTree(node.left)
    EndFunction

    // Start the conversion from the root
    convertToGreaterTree(root)

    Return root
EndFunction
                                    

Explanation

This algorithm leverages the properties of a BST to ensure that when we traverse the tree in reverse in-order order (right subtree, current node, left subtree), we visit nodes in descending order. By maintaining a running sum of all previously visited node values (lastSum), we can update each node to be the sum of its original value and all greater values in the BST. This results in the BST being transformed into a Greater Tree as required by the problem statement.