How to write a recursive function to search for a key in a binary tree using in-order traversal in C?

Question

I am trying to write a recursive function that, given the root of a binary tree and a key, searches for the key using in-order traversal. The function returns NULL if the node with the key isn't found; otherwise it returns the node containing the key.

What I'm having trouble with is returning the node that contains the key. Every time I call the function and the key is in the binary tree, the function returns NULL. It feels like the result keeps getting overwritten by the initialization in the first line in the function.

Here's the in-order search function:

typedef struct treeNode
{
    int data;
    struct treeNode *left, *right;
} TreeNode, *TreeNodePtr;

typedef struct
{
    TreeNodePtr root;
} BinaryTree;

TreeNodePtr inOrderKey(TreeNodePtr root, int key)
{
    TreeNodePtr node = NULL;

    if (root != NULL)
    {
        node = inOrderKey(root->left, key);
        if(key == root->data)
        {
           node = root;
           return node;
        }
        node = inOrderKey(root->right, key);
    }

    return node;
}

Here's the main function:

int main()
{
    FILE * in = fopen("numbst.txt", "r");

    BinaryTree bst;
    bst.root = NULL;

    int num;

    fscanf(in, "%d", &num);
    while (num != 0)
    {
        if (bst.root == NULL)
            bst.root = newTreeNode(num);
        else
        {
            TreeNodePtr node = findOrInsert(bst, num);
        }
        fscanf(in, "%d", &num);
    }

    printf("\nThe in-order traversal is: ");
    inOrder(bst.root);
    printf("\nThe pre-order traversal is: ");
    preOrder(bst.root);

    TreeNodePtr keyNode;
    int count = 0;
    keyNode = inOrderKey(bst.root, 9);
    if (keyNode != NULL)
        count = 1;
    else
        count = 0;

    if (count == 1)
        printf("\n\n%d exists in the binary tree. In order traversal was used.\n", 9);
    else
        printf("\n\n%d doesn't exist in the binary tree. In order traversal was used.\n", 9);
        return 0;
}

The in-order traversal of the binary tree I'm working with is: 1 2 3 4 5 7 9 21

The pre-order traversal of the binary tree is: 4 1 2 3 7 5 21 9

I'm testing the function using 9 and 31.

Answer 1

[edited - updated to use in order traversal]

Traverse left. If key not found, then check root, if key doesn't match, then recurse right.

TreeNodePtr inOrderKey(TreeNodePtr root, int key)
{
    TreeNodePtr node = NULL;
    if (root)
    {
        node = inOrderKey(root->left, key);
        if (node) {
            return node;
        }
        if (key == root->data)
        {
           return root;
        }
        node = inOrderKey(root->right, key);
    }
    return node;
}