CODEWITHSUNDEEP
javascriptbinary-search-tree
user7496931
user7496931

Reputation: 1519

Wrong recursion when trying to find Range Sum of BST

I'm practicing algorithms and tackling this classic problem. There are many solutions and I'm trying to solve it using Javascript. I'll post the question and what I have below:

Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).

The binary search tree is guaranteed to have unique values.

Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15 Output: 32

var rangeSumBST = function(root, L, R) {
    let result = 0;

    if (root === null) return 0;
    if (root.val >= L && root.val <= R) {
        result += root.val
    }
    rangeSumBST(root.left, L, R)
    rangeSumBST(root.right, L, R)

    return result
};
// Output is 10 instead of 32

Upvotes: 2

Views: 440

Answers (1)

Alex Vovchuk
Alex Vovchuk

Reputation: 2926

You are executing rangeSumBST(root.left, L, R) without using result from them. And finally get only first node value. Use instead:

var rangeSumBST = function(root, L, R) {
    let result = 0;

    if (root === null) return 0;
    if (root.val >= L && root.val <= R) {
        result += root.val
    }
    let left = rangeSumBST(root.left, L, R)
    let right = rangeSumBST(root.right, L, R)

    return result + left + right;
};

Upvotes: 3

Related Questions