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