QUESTION
Given a Binary Search Tree (BST) of integer values and a range [low, high], return count of nodes where all the nodes under that node (or subtree rooted with that node) lie in the given range.\n\nExamples:\n\nInput:\n 10\n / \\\n 5 50\n / / \\\n 1 40 100\nRange: [5, 45]\nOutput: 1 \nThere is only 1 node whose subtree is in the given range.\nThe node is 40 \n\n\nInput:\n 10\n / \\\n 5 50\n / / \\\n 1 40 100\nRange: [1, 45]\nOutput: 3 \nThere are three nodes whose subtree is in the given range.\nThe nodes are 1, 5 and 40.
ANSWER
#include<bits/stdc++.h>
using namespace std;
// A BST node
struct node
{
int data;
struct node* left, *right;
};
// A utility function to check if data of root is
// in range from low to high
bool inRange(node *root, int low, int high)
{
return root->data >= low && root->data <= high;
}
// A recursive function to get count of nodes whose subtree
// is in range from low to hgih. This function returns true
// if nodes in subtree rooted under 'root' are in range.
bool getCountUtil(node *root, int low, int high, int *count)
{
// Base case
if (root == NULL)
return true;
// Recur for left and right subtrees
bool l = (root->left) ? getCountUtil(root->left, low, high, count) : true;
bool r = (root->right) ? getCountUtil(root->right, low, high, count) : true;
// If both left and right subtrees are in range and current node
// is also in range, then increment count and return true
if (l && r && inRange(root, low, high))
{
++*count;
return true;
}
return false;
}
// A wrapper over getCountUtil(). This function initializes count as 0
// and calls getCountUtil()
int getCount(node *root, int low, int high)
{
int count = 0;
getCountUtil(root, low, high, &count);
return count;
}
// Utility function to create new node
node *newNode(int data)
{
node *temp = new node;
temp->data = data;
temp->left = temp->right = NULL;
return (temp);
}
// Driver program
int main()
{
// Let us construct the BST shown in the above figure
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 subtrees in [" << l << ", " << h << "] is " << getCount(root, l, h);
return 0;
}