bst-count.cpp

#include<iostream>
#include<stdio.h>

using namespace std;

typedef struct _NODE {
    int val;
    struct _NODE *left;
    struct _NODE *right;
    int weight;

} NODE;

NODE *head = NULL;
NODE* create_node(int x) {
    NODE *p = (NODE*)malloc(sizeof(NODE));
    p->val = x;
    p->left = NULL;
    p->right = NULL;
    p->weight = 1;
    return p;
}

int main() {
    int n;
    int k, x;
    scanf("%d", &n);
    for(int i = 0 ; i < n ; i++) {
        scanf("%d %d", &k, &n);
        NODE *ptr = head;
        if(k == 1){
            if (ptr == NULL) {
                head = create_node(x);
            }
            else {
                while(ptr != NULL) {
                    if(x <= ptr->val) {
                        if(ptr->left != NULL)
                            ptr = ptr->left;
                        else {
                            ptr->left = create_node(x);
                            break;
                        }
                    }
                    else {
                        ptr->weight++;
                        if(ptr->right != NULL)
                            ptr = ptr->right;
                        else {
                            ptr->right = create_node(x);
                            break;
                        }
                    }
                }
            }
        }
        else if(k == 2) {
            int count = 0;
            while(ptr != NULL) {
                if(ptr->val <= x) {
                    ptr = ptr->right;
                }
                else {
                    count += ptr->weight;
                    ptr = ptr->left;
                }

            }
            printf("%d\n", count);
        }
   }
}