Answer to Question #270181 in C for Amit

Question

Given a BST and a range low-to-high(inclusive). Write a C code to count the number of nodes in the BST that lie in the given range.

Answer 1

#include<stdio.h>
struct node
{
    int info;
    struct node* left, *right;
};
 
node *newNode(int info)
{
    node *temp = new node;
    temp->info  = info;
    temp->left  = temp->right = NULL;
    return (temp);
}
int getC(node *root, int low, int high)
{
  
    if (!root) return 0;
 
    if (root->info == high && root->info == low)
        return 1;
    if (root->info <= high && root->info >= low)
         return 1 + getC(root->left, low, high) +
                    getC(root->right, low, high);
 
    else if (root->info < low)
         return getC(root->right, low, high);
    else return getC(root->left, low, high);
}
 
int main()
{
    node *root        = newNode(8);
    root->left        = newNode(6);
    root->right       = newNode(30);
    root->left->left  = newNode(3);
    root->right->left = newNode(30);
    root->right->right = newNode(70);
    /* BST example
          8
        /    \
      6       30
     /       /  \
    3       30   70   */
    int l = 6;
    int h = 45;
    printf("Count of nodes between [");
	printf("%d",l); 
	printf(",%d ", h);
    printf("] is %d",getC(root, l, h));
    return 0;
}