-
-
Notifications
You must be signed in to change notification settings - Fork 0
/
CountBSTnodesthatlieinagivenrange.cpp
67 lines (58 loc) · 1.33 KB
/
CountBSTnodesthatlieinagivenrange.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node* right;
Node* left;
Node(int x){
data = x;
right = NULL;
left = NULL;
}
};
Node *insert(Node *root,int data)
{
if(root==NULL)
root=new Node(data);
else if(data<root->data)
root->left=insert(root->left,data);
else
root->right=insert(root->right,data);
return root;
}
// } Driver Code Ends
int getCountOfNode(Node *root, int l, int h)
{
if(!root)
return 0;
if(root->data==l && root->data==h)
return 1;
if(root->data>=l && root->data<=h)
return 1+getCountOfNode(root->left,l,h)+ getCountOfNode(root->right,l,h);
else if(root->data<l)
return getCountOfNode(root->right,l,h);
else
return getCountOfNode(root->left,l,h);
}
// { Driver Code Starts.
int main() {
int testcases;
cin>>testcases;
while(testcases--)
{
Node *root=NULL;
int sizeOfArray;
cin>>sizeOfArray;
int arr[sizeOfArray];
for(int i=0;i<sizeOfArray;i++)
cin>>arr[i];
for(int i=0;i<sizeOfArray;i++)
{
root=insert(root,arr[i]);
}
int l,h;
cin>>l>>h;
cout<<getCountOfNode(root,l,h)<<endl;
}
return 0;
} // } Driver Code Ends