lundi 6 juillet 2020

Print BST keys in the given range

QUESTION You are given an array of integers. First of all , You have to form a binary search tree from given integers. Now you have provided two integers k1 and k2. You have to print all nodes of BST within the range k1 and k2 (including k1 and k2).

INPUT FORMAT First line contains integer t as number of test cases. Each test case contains three lines. First line contains an integer n which is length of the array and second line contains n space separated integer. Third line contains the value of k1 and k2.

MY CODE

    #include<bits/stdc++.h>
using namespace std;
class node{
    public:
    int data;
    node*left;
    node*right;
    node(int d){
        data=d;
        left=right=NULL;
    }
};
node*Insert(node*root,int data){
    if(root==NULL)return new node(data);
    if(data<=root->data)root->left=Insert(root->left,data);
    else
    root->right=Insert(root->right,data);
    return root;

}
void PreOrder(node*root){
    if(root==NULL)return ;
    cout<<root->data<<" ";
    PreOrder(root->left);
    PreOrder(root->right);
}
void store(node*root,vector<int>&v,int l,int h){
    if(root==NULL)return;
    store(root->left,v,l,h);
    if(root->data>=l && root->data<=h)v.push_back(root->data);

    store(root->right,v,l,h);
   

}
vector<int> range(node*root,int l, int h){
    vector<int>v;
     store(root,v,l,h);
     sort(v.begin(),v.end());
     return v;


}
int main(){
    int test;
    cin>>test;
    for (int i=0;i<test;i++){
        node*root=NULL;
        int size;
        cin>>size;
        for (int i=0;i<size;i++){
            int data;
            cin>>data;
            root=Insert(root,data);
        }
       
        int l,h;
        cin>>l,h;
       cout<<"# Preorder : ";
        PreOrder(root);
        cout<<endl;
        vector<int>ans=range(root,l,h);
        cout<<"# Nodes with range are : ";
        for (auto x:ans){
            cout<<x<<" ";
        }
        cout<<endl;
    }
    return 0;
}

sample input::

no of test case 1 size 5 nodes 4 3 2 5 6 range 3 5

sample output

Preorder : 4 3 2 5 6

Nodes within range are : 3 4 5

PROBLEM

Wrong output for the nodes in the range my output

MY OUTPUT

Preorder : 4 3 2 5 6

Nodes with range are : 3 4 5 6

Aucun commentaire:

Enregistrer un commentaire