Range Sum of BST

BST:
        10
       / \
      5   15
     / \    \
    3   7    18

Range: [7, 15]

32

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int rangeSumBST(TreeNode* root, int low, int high) {
    // Base case: if the root is null, return 0
    if (root == nullptr) {
        return 0;
    }

    // Initialize the sum to 0
    int sum = 0;

    // If the current node value falls within the range, add it to the sum
    if (root->val >= low && root->val <= high) {
        sum += root->val;
    }

    // If the current node value is greater than the low value, explore the left subtree
    if (root->val > low) {
        sum += rangeSumBST(root->left, low, high);
    }

    // If the current node value is less than the high value, explore the right subtree
    if (root->val < high) {
        sum += rangeSumBST(root->right, low, high);
    }

    return sum;
}

int main() {
    // Construct the binary search tree for the sample input
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(5);
    root->right = new TreeNode(15);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(7);
    root->right->right = new TreeNode(18);

    int low = 7;
    int high = 15;

    // Find the sum of node values within the given range
    int sum = rangeSumBST(root, low, high);

    std::cout << "The sum of node values within the range [" << low << ", " << high << "] is: " << sum << std::endl;

    // Don't forget to free the allocated memory
    // ...

    return 0;
}