LeetCode 538. Convert BST to Greater Tree (javascript solution)

Description:

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

var convertBST = function(root) {
    // Keep track of the total during the traversal of the tree
    let sum = 0
    // Traverse right, middle, left and continually add to the sum
    function trans(root) {
        if(root === null) return 0;
        trans(root.right)
        root.val+=sum
        sum = root.val
        trans(root.left)
    }
    // Traverse the tree
    trans(root)
    return root
};