“Range Sum of BST” Javascript solution Cheat Sheet

The Range Sum of the BST challenge is in the easy category and is a good start for understanding more challenging algorithms using trees as a data structure. I will focus on explaining a solution that works and not on the O time and space complexity.

Challenge: “Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].”LeetCode

Note:

//Binary search tree data structure.
//Two integers low and high defined the range.
//Return sum of values within the range, including range values.

Example:

Input: root = [10,5,16,3,6,null,19], low = 6, high = 16
Nodes 6, 10, and 16 are in the range [6, 16]. 6 + 10 + 16 =32 
Output: 32
10
/\
5 16
/\ \
3 6 19

Explanation:

//Loop trought the left and right branch of the tree,
//check if node value is within the defined range,
//if it is then add it to the sum within the range,
// return the final sum of range values.

1. Sum result will be pushed to an array

sum = [];

2. Create a helper method for the node

function dsf(node){

3. If no node return null

if(!node) return null;

4. Starting by left branch then right

dsf(node.left)

dsf(node.right)

5. If the node value is greater or equal to low and smaller or equal to high it is within the range

if (node.val >= low && node.val <= high){

6. If within the range, push node value to the sum

sum.push(node.val)

console.log(sum)

7. Return sum by addition nodes values using reduce

return sum.reduce((a,b)=> a+b,0 )

Solution :

var rangeSumBST = function(root, low, high) {
sum = [];
function dsf(node){
if(!node) return null;
dsf(node.left)
high to be within the range
if (node.val >= low && node.val <= high){
sum.push(node.val)
}
dsf(node.right)
}
dsf(root)
console.log(sum)
return sum.reduce((a,b)=> a+b,0 )
};