QUESTION
Given a Binary Search Tree (BST) and a range, count number of nodes that lie in the given range.\n\nExamples:\n\nInput:\n 10\n / \\\n 5 50\n / / \\\n 1 40 100\nRange: [5, 45]\n\nOutput: 3\nThere are three nodes in range, 5, 10 and 40.
ANSWER
#include<bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node* left, *right;
};
node *newNode(int data)
{
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
int getCount(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 + getCount(root->left, low, high) +
getCount(root->right, low, high);
else if (root->data < low)
return getCount(root->right, low, high);
else return getCount(root->left, low, high);
}
int main()
{
node *root = newNode(10);
root->left = newNode(5);
root->right = newNode(50);
root->left->left = newNode(1);
root->right->left = newNode(40);
root->right->right = newNode(100);
int l = 5;
int h = 45;
cout << "Count of nodes between [" << l << ", " << h
<< "] is " << getCount(root, l, h);
return 0;
}