Go solution for Binary Search Tree to Greater Sum Tree

In this Leetcode problem, we are given a binary search tree, and we should replace all the values in the tree with the sum of all the node values that are higher or equal to the value of the node.

Problem statement

Note: Did you notice, that the mirror tree of the result is a binary search tree? :)

The thing I like to think about to make it simpler is assume that we have a sorted array. How would we resolve the problem with a sorted array? Well, we would traverse the array from the end to the start, recording the sum a we go, and update the values of the array.

We can do exactly that with a BST. How to go from the max to the min? We can do an in order traversal but switching right and left (a regular in-order traversal will give you min to max elements in a BST).

Then we keep track of the sum and pass it recursively. That is exactly what is done there:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func bstToGst(root *TreeNode) *TreeNode {
    // left-right in order traversal
    recBstToGst(root, 0)
    return root
}
func recBstToGst(root *TreeNode, preVal int) int {
    if (root == nil) {
        return preVal
    }
    res := recBstToGst(root.Right…