Convert BST to Greater Tree

Problem Statement

In this problem, you are provided with the root of a Binary Search Tree (BST) and your task is to transform this BST into a Greater Tree. In a Greater Tree, each node's key is reinvented by adding to its original key the sum of all the keys that are greater than the original key in the BST. It's important to understand how a BST functions:

• Each node in the left subtree of any node contains only keys less than that node's key.
• Each node in the right subtree will have keys that are greater than the node's key.
• Both left and right subtree structures themselves must adhere to the rules of BSTs.

Your resulting tree must meet these conditions by adjusting each node's value accordingly.

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 [0, 104].
• -104 <= Node.val <= 104
• All the values in the tree are unique.
• root is guaranteed to be a valid binary search tree.

Approach and Intuition

Understanding the Structure and Constraints:

• With node values ranging from -10⁴ to 10⁴ and up to 10⁴ nodes, handling large scales efficiently is crucial.
• All values being unique simplifies some parts of the BST operations since we don't need to handle duplicates.

Reversing the In-order Traversal Approach:

1. Normally, an in-order traversal of a BST (left-root-right) results in sorted order of the elements. However, by altering the traversal order to right-root-left, we effectively read the nodes in descending order.
2. Utilizing a running tally of the sums we've encountered, each node's value can be updated as we traverse.

Steps of the Transformation:

1. Start the traversal from the root. If the tree is empty (root is null), the resulting structure is also an empty tree.
2. Traverse the right subtree first. Every node visited adds its value to a cumulative sum.
3. Update the node's value by adding the cumulative sum to the node's original value.
4. Move to the left subtree and repeat the updating process.
5. This right-root-left traversal ensures each node is updated with the sum of nodes that have values greater than itself before the node itself is updated.

Example Analysis:

Example 1:

• Start from the largest element (rightmost node): The sum starts at 0. After visiting the node with the value 8, its sum becomes 8, and it remains 8 since there are no nodes with a value greater than 8. This node value will not change.
• Move to the node with value 7. It adds 8 (from its right child) to its current value making it 15, then update the sum to 15.
• Proceeding in this manner ensures that each node is correctly updated based on the greater values in the tree.

Example 2:

• A simpler case with only two nodes, the cumulative updating rule still follows, showing consistency for smaller inputs.

By following this approach of reversing the order of in-order traversal, converting any BST to its Greater Tree form can be efficiently achieved with clarity and precision.

Solutions

class Solution {
    // Retrieves the next higher node value
    private TreeNode getNextHigherNode(TreeNode current) {
        TreeNode nextNode = current.right;
        while (nextNode.left != null && nextNode.left != current) {
            nextNode = nextNode.left;
        }
        return nextNode;
    }

    public TreeNode convertBST(TreeNode root) {
        int totalSum = 0;
        TreeNode current = root;

        while (current != null) {
            if (current.right == null) {
                totalSum += current.val;
                current.val = totalSum;
                current = current.left;
            } else {
                TreeNode successor = getNextHigherNode(current);
                if (successor.left == null) {
                    successor.left = current;
                    current = current.right;
                } else {
                    successor.left = null;
                    totalSum += current.val;
                    current.val = totalSum;
                    current = current.left;
                }
            }
        }
        
        return root;
    }
}