Problem Statement:
You are given a root of BST and 2 values. You need to return the sum of the nodes that falls within the range.
Solution
For solution we follow below steps:
1. We take a node, and check if the node value is less than left, then we move to right.
2. We take a node, and check if the node value is greater than right, then we move to left.
Solution in C++
#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;
struct Node
{
int data;
struct Node *left, *right;
};
Node *get_new_node(int item)
{
Node *temp = new Node;
temp->data = item;
temp->left = temp->right = NULL;
return temp;
}
Node* insert_into_bst(Node* node, int data)
{
if (node == NULL) return get_new_node(data);
if (data < node->data)
node->left = insert_into_bst(node->left, data);
else if (data > node->data)
node->right = insert_into_bst(node->right, data);
return node;
}
void print_inorder(Node* Node)
{
if (Node == NULL)
return;
print_inorder(Node->left);
cout<<" "<<Node->data;
print_inorder(Node->right);
}
int get_range_sum_BST(Node *root, int L, int R)
{
if (root == NULL) return 0; // base case.
if (root->data < L) return get_range_sum_BST(root->right, L, R); // left branch excluded.
if (root->data > R) return get_range_sum_BST(root->left, L, R); // right branch excluded.
return root->data + get_range_sum_BST(root->right, L, R) + get_range_sum_BST(root->left, L, R);
}
int main()
{
Node *root_1 = NULL;
root_1 = insert_into_bst(root_1, 1);
insert_into_bst(root_1, 2);
insert_into_bst(root_1, 3);
insert_into_bst(root_1, 4);
insert_into_bst(root_1, 5);
cout<<"The range sum is "<<get_range_sum_BST(root_1, 4, 10)<<endl;
return 0;
}
Output:
The range sum is 9