Binary Search Tree to Greater Sum Tree

Problem Statement

In this task, we are given the root node of a Binary Search Tree (BST). We are required to transform this BST into what is known as a Greater Tree. In a Greater Tree, each node's new value is derived by summing the original key with all the keys in the BST that are greater than it. This requires a careful approach to ensure each node is updated correctly according to the constraints of the BST structure:

• Nodes in the left subtree are less than the node's key.
• Nodes in the right subtree are greater than the node's key.
• Both subtrees themselves abide by the rules of BSTs.

The challenge is to carry out this transformation while adhering to the BST properties and ensuring that each node is updated correctly with the sum of all greater keys plus its own.

Examples

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]

Constraints

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

Approach and Intuition

To solve this problem, let's leverage the inherent properties of a BST, particularly the ordering of elements when conducting an in-order traversal (left, root, right), which visits nodes in ascending order of their keys. However, since we are interested in the sum of all keys greater than the current key, a reversed in-order traversal (right, root, left) would be more applicable as it would visit nodes in descending order of their keys. This manner of traversal will allow us to maintain a running sum of all nodes visited thereby making it easy to update each node's value.

1. Initialize a variable sum to 0. This sum will hold the cumulative sum of all node values that have been visited during the traversal.
2. Start the reversed in-order traversal from the root. For each node:
   1. Recursively apply the transformation to the right subtree.
   2. Update the node's value by adding the running sum to the node's current value.
   3. Update the sum to include the node's updated value.
   4. Proceed to transform the left subtree.

Let's illustrate this approach using the examples given.

• Example 1:

  • The reversed in-order traversal would first visit 8 (the biggest element), updating the sum to 8 and thus the node to 8 itself.
  • Next, it would visit 7, and since the sum was previously updated to 8, the new value of 7 becomes 15 (7+8), updating sum again to 15.
  • This pattern continues until all nodes have been redefined as per the described rules, resulting in: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8].

• Example 2:

  • The traversal starts at 1, updating its value to 1 since there are no greater nodes.
  • With sum now at 1, 0 updates to 1 (sum+0).
  • The final output for this small tree is [1,null,1].

This approach ensures that each node is accessed and updated precisely once, and the use of the reversed in-order traversal perfectly aligns with the requirement to compute and utilize the sum of greater nodes.

Solutions

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;
    }
};