Solution For Range Sum Of Bst

Problem Statement:
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].

Example:
Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Node values in range [7, 15] are 7, 10, and 15. Their sum is 32.

Approach:
The problem is fairly simple. We will traverse the tree in inorder and add value of nodes that lie between the given range. Since it is a BST, the inorder traversal leads to nodes in ascending order of their value. Hence, if we find a node whose value is less than low, then there is no point of traversing in left subtree since all the nodes in the left subtree will have value less than low. Similarly, if we find a node whose value is greater than high, then there is no point of traversing in right subtree since all the nodes in the right subtree will have value greater than high. If the value of the node lies between [low, high], then add it to our sum and traverse the left and right subtree.

Algorithm:
1. Initialize the sum as 0.
2. Traverse the tree in inorder.
3. If the value of the node is less than low, then traverse the right subtree only.
4. If the value of the node is greater than high, then traverse the left subtree only.
5. If the value of the node lies between [low, high], then add it to our sum and traverse both left and right subtree.

Complexity:
Time complexity: O(N) – where N is the number of nodes in the tree. This is because in the worst case we will need to visit all the nodes.
Space complexity: O(H) – where H is the height of the tree. This is because the function will call itself recursively for each node in the path from the root to the leaf. In the worst case, this will be equal to the height of the tree.

Solution:

class Solution {
public:
int rangeSumBST(TreeNode* root, int low, int high) {
int sum = 0;
helper(root, low, high, sum);
return sum;
}

void helper(TreeNode* root, int low, int high, int& sum) {
    if(root == NULL)
        return;
    if(root->val >= low && root->val <= high) {
        sum += root->val;
        helper(root->left, low, high, sum);
        helper(root->right, low, high, sum);
    }
    else if(root->val < low)
        helper(root->right, low, high, sum);
    else
        helper(root->left, low, high, sum);
}

};

Step by Step Implementation For Range Sum Of Bst

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rangeSumBST(TreeNode root, int L, int R) {
        // base case
        if (root == null) {
            return 0;
        }
        
        // if current node's value is in the given range, include it in the sum
        // and continue recursion on both subtrees
        if (root.val >= L && root.val <= R) {
            return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
        // if current node's value is less than the lower bound, only continue
        // recursion on the right subtree
        } else if (root.val < L) {
            return rangeSumBST(root.right, L, R);
        // if current node's value is greater than the upper bound, only continue
        // recursion on the left subtree
        } else {
            return rangeSumBST(root.left, L, R);
        }
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
        
        #if root is None, return 0
        if not root:
            return 0
        
        #if root's value is less than L, then the range sum will only be in the right subtree
        if root.val < L:
            return self.rangeSumBST(root.right, L, R)
        
        #if root's value is greater than R, then the range sum will only be in the left subtree
        if root.val > R:
            return self.rangeSumBST(root.left, L, R)
        
        #if root's value is between L and R, then the range sum will be the root's value plus the range sums of the left and right subtrees
        return root.val + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R)

var rangeSumBST = function(root, L, R) {
    // base case
    if (!root) {
        return 0;
    }
    
    // if current node's value is in range, include it in sum
    // and recurse on left and right subtrees
    if (root.val >= L && root.val <= R) {
        return root.val + rangeSumBST(root.left, L, R) + rangeSumBST(root.right, L, R);
    }
    
    // if current node's value is less than L, recurse on right subtree
    // if current node's value is greater than R, recurse on left subtree
    if (root.val < L) {
        return rangeSumBST(root.right, L, R);
    } else {
        return rangeSumBST(root.left, L, R);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int L, int R) {
        if(!root) return 0; //if empty tree
        if(root->val < L) return rangeSumBST(root->right, L, R); //if root val is less than lower bound, all left tree vals will also be less
        if(root->val > R) return rangeSumBST(root->left, L, R); //if root val is greater than upper bound, all right tree vals will also be greater
        return root->val + rangeSumBST(root->left, L, R) + rangeSumBST(root->right, L, R); //if root val is in range, add it to the sum and recurse on left and right subtrees
    }
};

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int RangeSumBST(TreeNode root, int L, int R) {
        // Base case
        if (root == null) {
            return 0;
        }
        
        // Recursive case 1: If the current node's value is less than the lower bound,
        // then we know that we don't need to consider this node or its left subtree.
        if (root.val < L) {
            return RangeSumBST(root.right, L, R);
        }
        
        // Recursive case 2: If the current node's value is greater than the upper bound,
        // then we know that we don't need to consider this node or its right subtree.
        if (root.val > R) {
            return RangeSumBST(root.left, L, R);
        }
        
        // Recursive case 3: If the current node's value is between the lower and upper bounds,
        // then we know that we need to consider this node and both of its subtrees.
        return root.val + RangeSumBST(root.left, L, R) + RangeSumBST(root.right, L, R);
    }
}