Range Sum of BST easy

Problem Statement

Given the root node of a binary search tree (BST) and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1

Input: root = [10,5,15,3,7,null,18], low = 7, high = 15 Output: 32 Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32

Example 2

Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10 Output: 23 Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23

Steps

1. Recursive Approach: We will use a recursive function to traverse the BST.
2. Base Case: If the current node is nullptr, return 0.
3. Check Range: If the current node's value is within the range [low, high], add its value to the sum.
4. Recursive Calls: Recursively call the function for the left and right subtrees, only if they might contain nodes within the range. This pruning step is crucial for efficiency. If the node's value is less than low, we only need to explore the right subtree (since BST property). If the node's value is greater than high, we only need to explore the left subtree.

Explanation

The solution leverages the properties of a Binary Search Tree (BST). In a BST, all nodes in the left subtree of a node have values less than the node's value, and all nodes in the right subtree have values greater than the node's value. This allows us to efficiently prune the search space. If the current node's value is less than low, there's no need to search the left subtree because all values there will be even smaller. Similarly, if the current node's value is greater than high, there's no need to search the right subtree.

Code

/**
 * 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 low, int high) {
        if (root == nullptr) {
            return 0;
        }

        int sum = 0;
        if (root->val >= low && root->val <= high) {
            sum += root->val;
        }

        // Pruning the search space based on BST properties
        if (root->val > low) {
            sum += rangeSumBST(root->left, low, high);
        }
        if (root->val < high) {
            sum += rangeSumBST(root->right, low, high);
        }

        return sum;
    }
};

Complexity

• Time Complexity: O(N) in the worst case, where N is the number of nodes in the BST. However, in many cases, it will be significantly less than O(N) due to the pruning of subtrees.
• Space Complexity: O(H) in the worst case, where H is the height of the BST. This is due to the recursive call stack. In a balanced BST, H is log(N), while in a skewed BST, H can be N.