Binary Search Trees: Return the sum of given range in BST.

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

 

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *