leetcode problem 538 https://leetcode.com/problems/convert-bst-to-greater-tree/description/

optimal.java

// Below is the online solution that keeps a running sum, no extra space is needed other than recursion stack
private int accumulatingSum = 0;

public TreeNode convertBST(TreeNode root) {
    // Reset the accumulating sum
    this.accumulatingSum = 0;
    this.reverseInorderTraversal(root);
    return root;
}

public void reverseInorderTraversal(TreeNode node) {
    if (node == null) {
        return;
    }
    this.reverseInorderTraversal(node.right);
    this.accumulatingSum += node.val;
    node.val = this.accumulatingSum;
    this.reverseInorderTraversal(node.left);
}