Program crashes when inserting a node in a binary tree

Question

I created the following library to insert,delete,search and print nodes in a binary tree.

#include <stdlib.h>

struct NODE
{
    int code;
    char subject[20];
    struct NODE *left;
    struct NODE *right;
};


void InOrder(struct NODE *R)
{
    if (R==NULL)
    return;
    InOrder(R->left);
    printf("%d %s\n",R->code,R->subject);
    InOrder(R->right);
}

void PreOrder(struct NODE *R)
{
    if (R==NULL)
    return;
    printf("%d %s\n",R->code,R->subject);
    InOrder(R->left);
    InOrder(R->right);
}

void PostOrder(struct NODE *R)
{
    if (R==NULL)
    return;
    InOrder(R->left);
    InOrder(R->right);
    printf("%d %s\n",R->code,R->subject);
}

struct NODE *Search(struct NODE *R,int CODE,struct NODE **father)
{
    if(R==NULL)
    return NULL;
    if(R->code==CODE)
    {
        *father=R;
        return R;
    }
    if (CODE<R->code)
    return Search(R->left,CODE,father);
    else
    return Search(R->right,CODE,father);
}

struct NODE * CreateNode(struct NODE T)
{
    struct NODE *tmp;
    tmp=(struct NODE *)malloc(sizeof(T));
    *tmp=T;
    tmp->left=tmp->right=NULL;
    return tmp;
}

int Insert(struct NODE **R,struct NODE ND)
{
    struct NODE *cur,*fath=NULL;
    cur=Search(*R,ND.code,&fath);
    if (cur)
    return 0;
    cur=CreateNode(ND);
    if(fath==NULL)
    *R=cur;
    else
    if(fath->code>ND.code)
    fath->left=cur;
    else
    fath->right=cur;
    return 1;
}

struct NODE *MinOfMax (struct NODE *ND)
{
    struct NODE *tmp;
    if (ND==NULL)
    return NULL;
    if(ND->right==NULL)
    return NULL;
    tmp=ND->right;
    while(tmp->left!=NULL)
    tmp=tmp->left;
    return tmp;
}

struct NODE* Delete(struct NODE *R, int code)
{
    if (R==NULL) 
    return R;
    if (code<R->code)
    R->left=Delete(R->left,code);
    else if (code>R->code)
    R->right=Delete(R->right,code);
    else
    {
        if (R->left==NULL)
        {
            struct NODE *temp=R->right;
            free(R);
            return temp;
        }
        else if (R->right==NULL)
        {
            struct NODE *temp=R->left;
            free(R);
            return temp;
        }
        struct NODE *temp=MinOfMax(R->right);
        R->code=temp->code;
        R->right=Delete(R->right,temp->code);
    }
    return R;
}

When i try to insert a node in the binary tree,the program crashes.Here is my main:

 int main(int argc,char* argv[])
{
    typedef struct NODE NODE;
    NODE *root=NULL;
    NODE tmp;
    Insert(&root,tmp);
    return 0;
}

I tried to assign static values (for example code=100 and subject="Physics") but still the program crashes.Should i malloc something,change anything in my header file or do something entirely different?I'm stuck here for hours without finding any solution.Most insert functions out there assume that i only have one integer as data in the node,but i need to pass the entire node.

Please add an output of the program, people can help you with better information :) — , May 28 '17 at 11:30
@wildplasser How should i initialise it?Should i malloc the root node? — John M., May 28 '17 at 11:30
It is a pointer. It should point so something, or be NULL. BTW: there are a few more errors in your Search() and Insert() functions) — wildplasser, May 28 '17 at 11:32
@wildplasser Could you point my errors please?I have put a lot of effort to create this header file. — John M., May 28 '17 at 11:34
I can't understand what you are trying to do because the `main`does nothing. You've to `malloc tmp`, insert some value in it and then try to insert it into the tree. — simo-r, May 28 '17 at 11:46
@BetaRunner Nevermind my original comment was pointless.My mistake was that i didn't initialise the root pointer to NULL. — John M., May 28 '17 at 11:52
' didn't initialise the root pointer to NULL' and you could not tell that from your debugger? — ThingyWotsit, May 28 '17 at 12:57
in Search() the `*father=R;` will *only* be executed if the value is already present in the tree. In all other cases, it will be pointing to the NULL pointer `fath` in Insert(). IMHO the whole logic can be greatly simplified by letting `Search()` return a pointer to pointer, instead of handing it down via arguments. — wildplasser, May 28 '17 at 14:43

gsamaras · Answer 1 · 2017-05-28T12:01:09.713

1

Your tmp node, which is going to be the newly inserted node is used uninitialized in your main(). Your compiler could have warned you for this, if you had used -Wall flag.

So let's take a look in your insert function:

int Insert(struct NODE **R, struct NODE ND)
{
    struct NODE *cur,*fath=NULL;
    cur = Search(*R, ND.code, &fath); // ND.code is junk, since ND is uninitialized
    ...
    return 1;
}

which likely causes the segmentation fault.

root is too, you could initialize it to NULL in main().

Not the cause of your problem, but Do I cast the result of malloc? No.

edited May 28 '17 at 12:01

answered May 28 '17 at 11:31

gsamaras

71,951
46
188
305

Compilers often don't diagnose use of uninitialized values (I have always found those in Valgrind) – Paul Stelian May 28 '17 at 11:35
I understand,but i guess i need to initialise it outside of the Insert function,right? – John M. May 28 '17 at 11:35
@PaulStelian correct, see my updated answer! Yes John. – gsamaras May 28 '17 at 11:36

score 1 · Accepted Answer · answered May 28 '17 at 11:51

1

Your code basically does nothing. It seems you copy-pasted it from somewhere. I tried to figure it out and here's a code example. Basically you've to initializate a new node in the main when you try to insert it. Note that's just an example, i didn't a full test.

int main(int argc,char* argv[])
{
    typedef struct NODE NODE;
    NODE *root=NULL;
    NODE *tmp = malloc(sizeof(struct NODE));
    tmp->code = 1; /*Just a number*/
    strcpy(tmp->subject,"prova"); /*Put something in it*/
    Insert(&root,*tmp); /* Try to insert it*/
    PreOrder(root); /*Try to see if it has been inserted*/
    return 0;
}

answered May 28 '17 at 11:51

simo-r

733
1
9
13

Thanks for the answer,it was my fault that i didn't initialise the root pointer to NULL.Now my program works properly. – John M. May 28 '17 at 11:58
@JohnM. you should mark the answer as correct dude. – simo-r May 28 '17 at 12:00

Program crashes when inserting a node in a binary tree

2 Answers2