BSTQ

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int data;
    Node *left,*right;
    int lCount;
    Node(int x)
    {
        data=x;
        left=right=NULL;
        lCount=0;
    }
};
Node* root;

Node* insert(Node* root,int x)
{
    if(root==NULL)
        return new Node(x);
    if(x<root->data)
    {
        root->left=insert(root->left,x);
        root->lCount++;
    }
    else
        if(x>=root->data)
            root->right=insert(root->right, x);
    return root;
}

Node* kthSmallest(Node* root,int k)
{
    if(root==NULL)
        return NULL;
    int count=root->lCount+1;
    if(count==k)
        return root;
    if(count>k)
        return kthSmallest(root->left,k);
    return kthSmallest(root->right,k-count);
}

int main()
{
    int n,c,nr;
    ifstream fin("bstq.in");
    fin>>n;
    ofstream fout("bstq.out");
    while(n--)
    {
        fin>>c>>nr;
        if(c==1)
            root=insert(root,nr);
        else
        {
           Node* res=kthSmallest(root,nr);
            if(res==NULL)
                fout<<0<<'\n';
            else
                fout<<res->data<<'\n';
        }
    }
    return 0;
}