Sum of bst tree nodes with in certain range

Question

var rangeSumBST = function(root, low, high) {
    let sum=0;

    if(root){
        sum+=(root.val>=low&&root.val<=high)?root.val:0;
        sum+=rangeSumBST(root.left,low,high);
        sum+=rangeSumBST(root.right,low,high);
    }
    
    return sum;
};

This is the function to find sum of values between certain range.

My doubt here is if we give sum =0 everytime it won't be initialized to zero.

Can anyone help me in understanding recursion concept here.

Can anyone provide link for recursion.

Answer 1

The function is fine, but it is a pity that it visits every node of the tree. You can use if conditions to guard recursive calls which are sure to return 0, because their range (according to the BST property) is guaranteed to be outside the low/high range given to the function:

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;
};

If it is known that the BST will not have duplicate values, the if conditions can drop the equality condition... so root.val > low and root.val < high.

My doubt here is if we give sum =0 everytime it won't be initialized to zero.

There is no problem there. Be aware that every call of rangeSumBST creates an execution context that has its own local variables. So for example, let sum = 0 will only affect that local variable, and not the variables with the same name that live in other execution contexts of the same function.

Each call is responsible for the tree that it is given the root of, and will return the value of its sum variable to the caller, after which that execution context disappears -- including that sum variable. Then the caller trusts that this result is correct for its child tree, and accumulates it into its own sum.