Convert Binary Search Tree to Greater Tree

Problem: Convert a Binary Search Tree to a Greater Tree such that every node's value of the original BST is changed to sum of original node's value and sum of all the values in BST which are greater than original node's value.

Example:

Input: The binary search tree in the above image with blue nodes.
Output: The values of node will be changed to the values in the rectangle box in the above image. 

Approach: We can use reverse Pre-Order traversal here (first right and then left) and keep the previous sum in the recursive calls. Here are the changes that we need to apply:

• previous_sum = previous_sum + node.Value
• node.Value = previous_sum

Implementation in C#:

        public void ToGreaterTree()

        {

            if (this.Root == null)

            {

                return;

            }

            int prevSum = 0;

            this.ToGreaterTree(this.Root, ref prevSum);

        }

        private void ToGreaterTree(BinaryTreeNode node, ref int prevSum)

        {

            if (node != null)

            {

                this.ToGreaterTree(node.RightNode, ref prevSum);

                prevSum += node.Value;

                node.Value = prevSum;

                this.ToGreaterTree(node.LeftNode, ref prevSum);

            }

        }

Complexity: O(n)