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.

Shouldn't the test for if(key == root->data) be above the first recursive call? — Todd, Feb 15 '20 at 01:07
I thought the test for if (key == root->data) was supposed to be after the first recursive call because I'm looking for the key using in-order traversal? — Dante, Feb 15 '20 at 01:11
I believe it would though. Anyway, the way the code is above, it'll miss the case where you hit the target node because the if statement needs to happen before continuing the recursion. — Todd, Feb 15 '20 at 01:11
Say that on the first call you give it a root node that has data matching the key. You should test for that first before calling left recursion. — Todd, Feb 15 '20 at 01:15
Note the discussion in [Is it a good idea to typedef pointers?](https://stackoverflow.com/q/750178/15168) TL;DR — in general, the answer is "No", with a possible exception for function pointers. — Jonathan Leffler, Feb 15 '20 at 02:41

Eric Postpischil · Answer 1 · 2020-02-15T14:51:08.740

2

This code:

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

first uses inOrderKey to search the left subtree. Then it ignores the result.

Then it tests whether the current node contains the key. If it does, it returns to its caller. If the caller was itself (this is in a recursive call, not the original), the caller likely ignores the result.

Then it uses inOrderKey to search the right tree. Then it returns the result.]

Ultimately, the node containing the key will be returned only if it was in the rightmost path. If it is in the left subtree of any node, it will be ignored.

To fix this, after each call to inOrderKey, test whether the returned value is a null pointer. If it is not, return it immediately instead of going on.

edited Feb 15 '20 at 14:51

answered Feb 15 '20 at 01:11

Eric Postpischil

195,579
13
168
312

Incidentally, this presumes you really want to search via in-order traversal, as the question states. Of course, a major purpose of binary trees is to keep them in order so that you can intelligently search **only** the left subtree or the right subtree at each point. However, you might need to do an in-order traversal when looking for something other than the key that was used to order the tree. Or when completing a class exercise requiring in-order traversal. – Eric Postpischil Feb 15 '20 at 01:13
I tried this solution, but somehow I'm still getting the wrong result. I typed, if (node != NULL) return node after each recursive call. Does initializing node = NULL in the first line of the function cause it to return NULL every time? Also, this question came from a data structures book I'm going through not from a class. I really struggle with recursive binary tree problems so I'm just working through the book. – Dante Feb 15 '20 at 02:13
@EricPostpischil, you are assuming the binary tree is ordered with the same criteria used to find the key. That is gratuituous, the key you are searching for doesn't have to be the one used to build the binary tree (indeed no order is assumed on the keys used, just a search request for equality) – Luis Colorado Feb 15 '20 at 14:01
@Dante, I'm afraid EricPostischil is only showing you the code snippet that has to be modified, not the right answer, as that code continues to ignore the result from the left child. – Luis Colorado Feb 15 '20 at 14:03
@LuisColorado: I made no such assumption. The changes I indicate in this answer find the sought node regardless of its location in the tree (because they search every node, so the desired node must be found if it is present), and they continue (as the code in the question does) to traverse the tree in order, as requested in the question. My first comment states this; this answer tells how to do the search using in-order traversal, without using any information about the ordering of the tree. – Eric Postpischil Feb 15 '20 at 14:48
no... continuing traversing the tree has no sense.... so better to return.... The assumption is to traverse it in in-order sequence.... so, for each node you have to traverse first the left subtree, then the node itself, then the right subtree.... but once you find the node it's of no use at all to continue searching at all.... this is what the asker does, and this is how he destroys the info he has got. The marked solution navitages in pre-order, so that makes me thing he has no clear idea of what he wants, because he cannot distinguish pre-order traversal against in-order. – Luis Colorado Feb 15 '20 at 16:26
@LuisColorado: My answer does not say to continue traversing the tree once the target has been found. It says the opposite: “after each call to inOrderKey, test whether the returned value is a null pointer. If it is not, return it immediately instead of going on.” – Eric Postpischil Feb 15 '20 at 16:45
@EricPostpischil, your answer is not the marked one. I'm not talking about your answer, but about your comment above. You talk about _the conservation of the tree ordering_, which is something traversal (in any way) don't touch. Anyway, it is not so important to continue the discussion, so please, allow me to abandon it at this point. Thanks. – Luis Colorado Feb 15 '20 at 16:56

score 1 · Answer 2 · answered Feb 15 '20 at 13:56

The problem you have is that you insist in navigating the whole tree without checking if you found the key already. In

TreeNodePtr inOrderKey(TreeNodePtr root, int key)
{
    /* don't declare a local you don't know 
     * yet if you are going to use */

    /* better to check the opposite */
    if (root == NULL) 
        return NULL;  /* no tree, nothing can be found */

    TreeNodePtr node = inOrderKey(root->left, key);

    if (node) return node; /* we found it in the left child */
    if(key == root->data) { /* check here */
        /* you found it in this node */
        return root;
    }

    /* last chance, right child :) */
    return inOrderKey(root->right, key);
}

the verifications are made, so this should work (I've not tested it, as you didn't post a complete and verifiable example, my apologies for that)

Looks good to me. Thanks for catching my misunderstanding of in-order traversal. I've updated my answer. — Todd, Feb 15 '20 at 20:41

Todd · Accepted Answer · 2020-02-15T20:01:59.513

0

[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;
}

edited Feb 15 '20 at 20:01

answered Feb 15 '20 at 01:21

Todd

4,669
1
22
30

I tried this, but when I search for a number that's not in the binary tree it says it exists. – Dante Feb 15 '20 at 01:37
What code is testing for whether it found the node? – Todd Feb 15 '20 at 01:40
What code not included in the original code you posted outside of this function is calling it and then testing whether it found the target node or not? can you post that as well? – Todd Feb 15 '20 at 01:49
I included the main function. Thanks for your help. – Dante Feb 15 '20 at 01:55
When you try this specific implementation, if you're getting errors.. i'm pretty sure the bug isn't here =) – Todd Feb 15 '20 at 02:15
I just realized I put 91 there instead of 9. I was running different cases and forgot to change it back. It works thanks. – Dante Feb 15 '20 at 02:24
Yeah.. I saw that too.. and was going to ask.. but I figured you already knew! You're welcome =) – Todd Feb 15 '20 at 03:09
I'm afraid this will work, but is never a in-order navigation, but a preorder one. You first check the root node (navigate the root) then go for left and right children. And that's pre-order... not in-order. – Luis Colorado Feb 15 '20 at 14:06
you're correct. By definition "in order traversal" is to check the left subtree, check root, traverse right: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/ I updated the code. Thanks. – Todd Feb 15 '20 at 18:55

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

3 Answers3