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.