Двоичное дерево поиска с повторяющимися значениями и числом узлов больше / меньше введенного значения?

Question

Я пытаюсь разработать двоичное дерево поиска, которое может хранить повторяющиеся значения. Пожалуйста, смотрите проблему ниже.

Пример:

Ниже приведен мой код:

#include<stdio.h>
#include<stdlib.h>

long int N=0; //Total number of nodes present
struct node
{
    long int key;
    long int count;
    struct node *left, *right;
};

struct node* make(long int key) //To make a node
{
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->key = key;
    temp->left = temp->right = NULL;
    temp->count = 1;
    return temp;
}

void inOrder(struct node *root) //Traverse inorder
{
    if (root != NULL)
    {
        inOrder(root->left);
        printf("%ld(%ld) ", root->key, root->count);
        inOrder(root->right);
    }
}

struct node* learn(struct node* node, long int key) //Insert Node
{

    if (node == NULL){
        N++;
        return make(key);
    }

    if (key == node->key){
        N++;
        (node->count)++;
        return node;
    }

    if (key < node->key)
        node->left = learn(node->left, key);
    else
        node->right = learn(node->right, key);

    return node;
}

struct node * minValueNode(struct node* node)
{
    struct node* current = node;
    while (current->left != NULL)
        current = current->left;

    return current;
}
//Completely delete the node
struct node* forget(struct node* root, long int key)

{
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = forget(root->left, key);

    else if (key > root->key)
        root->right = forget(root->right, key);

    else {
        N += -(root->count);
            if ((root->left == NULL) || (root->right == NULL)) {
            struct node* temp = root->left ? root->left : root->right;

            if (temp == NULL) {
                temp = root;
                root = NULL;
            }
            else
                *root = *temp;
            free(temp);
        }
        else {
            struct node* temp = minValueNode(root->right);

            root->key = temp->key;
            root->count = temp->count;
            temp->count = 1;

            root->right = forget(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

    return root;
}
//Decrease the count of node key by value n
struct node* decrease(struct node* root, long int key, long int n){

    if (root == NULL) return root;

    if (key < root->key)
        root->left = decrease(root->left, key, n);


    else if (key > root->key)
        root->right = decrease(root->right, key, n);

    else{
        if (root->count > 1 && n < root->count){
            N += -n;
            (root->count) += -n;
            return root;
        }

        N += -(root->count);
        if (root->left == NULL)
        {
            struct node *temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL)
        {
            struct node *temp = root->left;
            free(root);
            return temp;
        }

        struct node* temp = minValueNode(root->right);
        root->key = temp->key;
        root->right = decrease(root->right, temp->key, n);
    }
    return root;
}
//Find number of nodes larger than key
void largerNums(struct node* root, long int key, long int* lnums){
    if (root == NULL)
        return;

    if (key < root->key){
        (*lnums) += root->count;
        largerNums(root->right, key, lnums);
        largerNums(root->left, key, lnums);
    }
    else if (key >= root->key)
        largerNums(root->right, key, lnums);

    return;
}

//Find number of nodes smaller than key
void smallerNums(struct node* root, long int key, long int* snums){
    if (root == NULL)
        return;

    if (key <= root->key){
        smallerNums(root->left, key, snums);
    }
    else if (key > root->key){
        (*snums) += root->count;
        smallerNums(root->left, key, snums);
        smallerNums(root->right, key, snums);
    }
    return;

}
//Find key'th element in ascending order
void asc(struct node* root, long int key, long int* cnt){

    if (root != NULL) {
        asc(root->left, key, cnt);
        int i;
        for(i=1; i <= (root->count); ++i){
            (*cnt)++;
            if(*cnt == key){
                printf("%ld\n", root->key);
                return;
            }
        }
        asc(root->right, key, cnt);
    }

}

//To compare strings
int myStrCompare(char a[], char b[]){
   int c = 0;

   while (a[c] == b[c]) {
      if (a[c] == '\0' || b[c] == '\0')
         break;
      c++;
   }

   if (a[c] == '\0' && b[c] == '\0')
      return 0;
   else
      return -1;
}
//To know which command user entered
int myCompare(char *str){

    if(myStrCompare(str, "learn") == 0)
        return 1;
    else if(myStrCompare(str, "forget") == 0)
        return 2;
    else if(myStrCompare(str, "decrease") == 0)
        return 3;
    else if(myStrCompare(str, "smaller_nums") == 0)
        return 4;
    else if(myStrCompare(str, "larger_nums") == 0)
        return 5;
    else if(myStrCompare(str, "asc") == 0)
        return 6;

    return -1;
}

int main()
{
    long int i, q, x, n, lnums, snums, cnt=0;
    int choice;
    char input[100];
    struct node* root= NULL;

    scanf("%ld", &q);
    //printf("%s", input);

    for(i=1; i<=q; ++i){
        scanf("%s", input);
        //printf("%s", input);
        choice = myCompare(input);
        //printf("\n%d", choice);

        switch(choice){
            case 1: scanf("%ld", &x);
                root = learn(root, x);
                break;
            case 2: scanf("%ld", &x);
                root = forget(root, x);
                break;
            case 3: scanf("%ld%ld", &x, &n);
                if(n < 1){
                    break;
                }else{
                    root = decrease(root, x, n);
                }
                break;
            case 4: scanf("%ld", &x);
                snums = 0;
                smallerNums(root, x, &snums);
                printf("%ld\n", snums);
                break;
            case 5: scanf("%ld", &x);
                lnums = 0;
                largerNums(root, x, &lnums);
                printf("%ld\n", lnums);
                break;
            case 6: scanf("%ld", &x);
                if(x > N){
                    printf("%d\n", -1);
                    break;
                }else{
                    cnt=0;
                    asc(root, x, &cnt);
                }
                break;
            /*case -1: inOrder(root);  \\to know the current state of tree
                printf(" N= %ld \n", N); \\to know total number of nodes
                */ 

        }
    }
   /* root = learn(root, 5);
    root = learn(root, 2);
    root = learn(root, 7);
    root = learn(root, 3);
    root = learn(root, 2);
    smallerNums(root, 5, &s);
    printf("\n%ld\n", s);
    largerNums(root, 2, &l);
    printf("%ld\n", l);
    asc(root, 2, &cnt); cnt = 0;
    root = decrease(root, 2, 1);
    asc(root, 2, &cnt); cnt = 0;
    inOrder(root); printf("\n");
    root = forget(root, 7);
    printf("\n"); inOrder(root);
    l=0;
    largerNums(root, 2, &l);
    printf("%ld\n", l);
    root = forget(root, 5);
    l=0;
    largerNums(root, 2, &l);
    printf("%ld\n", l);
*/


    return 0;
}

Мой код проходит образец тестового примера, однако, когда я отправляю свой код, я получаю TLE в 2 тестовых случаях в 2 неправильных тестовых случаях ( из 10)

Я не могу понять, что происходит в моем коде. Я потратил почти 5 дней, пытаясь выяснить. Если вы, ребята, можете мне помочь, тогда я буду благодарен.

Причина, по которой я подозреваю TLE, связана с функцией lowerNums и largeNums, потому что в этих функциях я рекурсивно посещаю каждый (почти) узел. Было бы здорово, если бы вы, ребята, могли сказать мне, как я могу сохранить размер поддерева в каждом узле, чтобы мне не пришлось обходить все это дерево.