Binary Search Trees: Count the number of BST nodes that lie in a given range.

Solution

The solution is very simple.

For every node visited, check if the node lies in range, if yes, then increment the count. Then recursion for both of its children.

If the current node is smaller than low value, then recursion the right child, else recursion the left child.

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_count(Node *root, int low, int high)
{
    if (!root) return 0;
  
    if (root->data == high && root->data == low)
        return 1;
  
    if (root->data <= high && root->data >= low)
         return 1 + get_count(root->left, low, high) +
                    get_count(root->right, low, high);
  
    else if (root->data < low)
         return get_count(root->right, low, high);
  
    else return get_count(root->left, low, high);
}

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 count is "<<get_count(root_1, 4, 10)<<endl;

    return 0;
}

Output:

The count is 2