COUNT BST subtrees until finding specific given key (inorder traversal)

Question

Homework assignment

I need to count how many subtrees I went through (inorder) until found the given key,

for example: if I have a tree, & it's inorder traversal is: 1,3,7,8,9,10,11,15,20 when given key:9, I need to return 5, when given key:3, I need to return 2. I have been all over the internet trying to find some help & couldn't find.

What I got so far is:

(The "FUNC" is a specific function that compares integers or whatever, it works)

    void PRINT_KEY_ORDER(PTN TRoot, void *nkey, CMP_KEYS FUNC)  // prints keys place (inorder)
{
    int counter = 1;
    fprintf(stdout, "%d", *(COUNT_INORDER(TRoot, nkey, FUNC, &counter)));   // prints counter which is always INT
}

int* COUNT_INORDER(PTN TRoot, void *nkey, CMP_KEYS FUNC, int *counter)      // counts times until reaches wanted key
{
    if (TRoot != NULL)
    {
        COUNT_INORDER(TRoot->left, nkey, FUNC, counter);
        if (FUNC(TRoot->key, nkey) == 0)
            return counter;
        (*counter)++;
        COUNT_INORDER(TRoot->right, nkey, FUNC, counter);
    }
}

this code works.

Counts correctly but for some reason crashes on the fprintf line if I use more than these: 9 3 1 7 8 20

Answer 1

Not sure if this is correct. Try to go inorder and increase count in a static variable. Once key is found put that as the return variable, otherwise the default return is -1 for key not found.

int COUNT_INORDER(PTN TRoot, nkey, FUNC )     
   {
    static count=0;
    int ret=-1;

    ret= COUNT_INORDER(TRoot->left, nkey, FUNC);

    count++;
    if (FUNC(TRoot->key, nkey) == 0)
        ret = count;

    if(ret == -1)
        ret= COUNT_INORDER(TRoot->right, nkey, FUNC);


     return ret;
    }