Inserting a binary search tree in C

Question

I tried to create a binary search tree by using the insert function.
The the result was not what I expected, it only yielded the first
value of the node of the tree. Can anyone find out what is the problem?
Thank you!

And can someone check if my other functions are right too?

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    struct node* left;
    struct node* right;
    int val;
}treeNode;
int searchTree(treeNode *T, int key, treeNode *T1, treeNode** p)
{
    if(!T)
    {
        *p=T1;
        return 0;
    }
    else if(T->val==key)
    {
        *p=T;
        return 1;
    }
    else if(T->val<key)
    {
        searchTree(T->right,key,T,p);
    }
    else
    {
        searchTree(T->left,key,T,p);
    }
    return 1;
}
int insert(treeNode **T, int key)
{
    treeNode *p;
    treeNode *s;
    if(!searchTree(*T,key,NULL,&p))
    {
        s= malloc(sizeof(treeNode));
        s->val=key;
        s->left=s->right=NULL;
        if(!p)      
       {
            *T=s;
        }
        else if(p->val<key)
        {
            p->right=s;
        }
        else
        {
            p->left=s;
        }
    }
    else
    {
        return -1;
    }
    return 1;
}
int delete(treeNode **T)
{
    treeNode *q;

    if(!(*T)->left)
    {
        q=*T;
        *T=(*T)->right;
        free(q);
    }
    else if(!(*T)->right)
    {
        q=*T;
        *T=(*T)->left;
        free(q);
    }
    else
    {
        treeNode *s;
        q=*T;
        s=(*T)->right;
        while(s->left)
        {
            q=s;
            s=s->left;
        }
        (*T)->val=s->val;
        if(q!=*T) q->left=s->right;
        else q->right=s->right;
        free(s);
    }
    return 1;
}
void preOrder(treeNode *T)
{
    if(!T)  return;
    preOrder(T->left);
    printf("%d\n",T->val);
    preOrder(T->right);
}
int main() {
    int a[10]={62,88,58,47,35,73,51,99,37,93};
    treeNode *T=NULL;
    for(int i=0;i<10;i++)
    {
        insert(&T,a[i]);
    }
    preOrder(T);
    return 0;
}

The result is 62 rather than the whole array!

Your searchTree returns 0 if the tree is empty, otherwise it returns 1. So only only the first call to insert will insert a node and return 1, and the other calls to insert will return -1. Your searchTree should probably return the result from the recursive call to searchTree. — Ian Abbott
– Ian Abbott, Commented Mar 26, 2019 at 16:22
did you see the code examples on en.wikipedia.org/wiki/Binary_search_tree? — rustyMagnet
– rustyMagnet, Commented Mar 26, 2019 at 16:34

4386427 · Accepted Answer · 2019-03-26 16:34:59Z

2

The problem is the return value from searchTree. When you do recursive calls you need to pick up the return value from those recursive calls. Like:

int searchTree(treeNode *T, int key, treeNode *T1, treeNode** p)
{
    if(!T)
    {
        *p=T1;
        return 0;
    }
    else if(T->val==key)
    {
        *p=T;
        return 1;
    }
    else if(T->val<key)
    {
        return searchTree(T->right,key,T,p);  //notice the return
    }
    else
    {
        return searchTree(T->left,key,T,p);  // notice the return
    }
    return 1;  // Not really needed...
}

answered Mar 26, 2019 at 16:34

4386427

44.7k4 gold badges44 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Liu Over a year ago

Thank you very much

Liu Over a year ago

why do I need to pick up the return values from recursive calls??

bruno · Accepted Answer · 2019-03-26 17:00:31Z

0

Your search function does not work as you expect

You can just remove it and do :

int insert(treeNode ** t, int key)
{
  if (*t == NULL)
  {
    treeNode * s = malloc(sizeof(treeNode));

    s->val=key;
    s->left=s->right=NULL;
    *t = s;
  }
  else if ((*t)->val == key) /* I am not sure but it seems you do not want to insert several times the same key, else that case */
    return -1;
  else if((*t)->val < key)
    insert(&(*t)->right, key);
   else
     insert(&(*t)->left, key);

   return 1;
}

as you see the code is much more simple ... and it works

Compilation and execution

pi@raspberrypi:/tmp $ gcc -g -pedantic -Wextra -Wall t.c
pi@raspberrypi:/tmp $ ./a.out
35
37
47
51
58
62
73
88
93
99

Your delete function doesn't work, if I add delete(&t); at the end of the main and I execute under valgrind there are memory leaks :

==14950==    definitely lost: 12 bytes in 1 blocks
==14950==    indirectly lost: 96 bytes in 8 blocks

A simple way to do is :

void delete(treeNode **t)
{
  if (*t != NULL) {
    delete(&(*t)->left);
    delete(&(*t)->right);
    free(*t);
    *t = NULL;
  }
}

After that change there is no memory leaks

edited Mar 26, 2019 at 17:00

answered Mar 26, 2019 at 16:26

bruno

34.3k8 gold badges31 silver badges48 bronze badges

6 Comments

Liu Over a year ago

Thank you so much! We meet again!!

bruno Over a year ago

@Liu yes, again ^^ Warning I supposed you do not want several times the same key, may be I was wrong, remove the associated code if needed

Liu Over a year ago

Your solution is better, but I still want to know what is the problem of my code.

bruno Over a year ago

@Liu your delete function doesn't work because you have memory leaks and it is very complicated for nothing

bruno Over a year ago

@Liu step by step ^^ I let you fixing the delete or I give you the solution ?

|

Collectives™ on Stack Overflow

Inserting a binary search tree in C

2 Answers 2

2 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related