Count BST nodes that lie in a given range

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro