938. Range Sum of BST (javascript solution)

#algorithms #javascript

Description:

Given the root node of a binary search tree, return the sum of values of all nodes with a value in the range [low, high].

Solution:

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

// Depth first search approach
// Add calculate the sum of right side + left side + root node
// Only add nodes to the sum if they fill in the range
var rangeSumBST = function(root, low, high) {
    if(!root) return 0;
    let sum = root.val >= low && root.val <= high ? root.val : 0;
    if(root.val >= low) sum += rangeSumBST(root.left, low, high)
    if(root.val <= high) sum += rangeSumBST(root.right, low, high)

    return sum
};