Marc Lester Tan

The solution to this medium LC problem involves traversing the tree using inorder traversal. In-order traversal means the left node gets the priority, followed by the root node then right node.

To solve this problem, we traverse the tree using inorder traversal and then collect the nodes as we go along. Finally, loop through all the collected nodes starting from the end and compute the new values for each node by adding the current node’s value with the next one.

class Solution {
    fun bstToGst(root: TreeNode?): TreeNode? {
       tailrec fun inorder(node: TreeNode?, collector: MutableList<TreeNode>) {
           if(node == null) return
           inorder(node.left, collector)
           collector.add(node)
           inorder(node.right, collector)
       }
       
       var collector = mutableListOf<TreeNode>()
       inorder(root, collector)
       
       (collector.size - 2 downTo 0).forEach {
           collector[it].`val` += collector[it + 1].`val`
       }
       
       return root
    }
}

Runtime: 148 ms, faster than 29.17% of Kotlin online submissions for Binary Search Tree to Greater Sum Tree.
Memory Usage: 32.3 MB, less than 100.00% of Kotlin online submissions for Binary Search Tree to Greater Sum Tree.