Range Sum Of Bst - Leetcode Solution

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

};

1