Binary Search Tree with pointers in C

Question

I'm new in C. My task is to implement Binary Search Tree. So, I'm really confused with pointers. Though, the concept is clear in trivial cases but using pointers in structures is confusing for me.

I have header

#include <stdio.h>

typedef struct node_st {
int value;
struct node_st *leftchild;
struct node_st *rightchild;
} node;

typedef struct tree_st {
    int size;
    node root; 
} tree;  

extern void insert(tree *t, int value);

I want to implement insert. Here is my attempt

extern void insert(tree *t, int value) {

int size = t->size;

node insertNode;
node *toInsert = &insertNode; 
toInsert->value = value;                  
toInsert->leftchild = NULL;
toInsert->rightchild = NULL;

if(size == 0) {
    t->root = toInsert; 
    t->size++; 
} else {

    node *current; 
    current = t->root;                  

    for(int i = 0; i < size; ++i) {

        if(current->value < value) {
            if(current->rightchild != NULL) {
                current = current->rightchild; 
            }
            else {
                current->rightchild = toInsert;
                t->size++; 
                break;      
            }
        } else if(current->value > value) {
            if(current->leftchild != NULL) {
                current = current->leftchild; 
            }
            else {
                current->leftchild = toInsert;
                t->size++; 
                break;      
            }
        } else {
            printf("The value has been already inserted"); 
        }
    }


}
}

I get the following error:

/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/Scrt1.o: In function _start': (.text+0x20): undefined reference tomain' collect2: error: ld returned 1 exit status

Questions & Problems:

What that error means?
Are all pointers in the function correct?
Is it necessary to define root as a pointer in struct node_st at all?

OT: for(int i = 0; i < size; ++i) { could simply be while(1) { — 4386427
– 4386427, Commented Oct 14, 2018 at 7:40

Rabbid76 · Accepted Answer · 2018-10-14 07:39:27Z

1

node insertNode; is a local variable declared in the scope of the function insert.
If the function terminates, then the variable is lost.

You have to allocate a dynamic node, by malloc:

node *toInsert = malloc(sizeof(node ));

In the struct tree_st, the element root is not a pointer to a node, but it is a node itself.
This causes that the assignment t->root = toInsert; doesn't work, because toInsert is a pointer to a a node.

Change the data type struct tree_st to make it work. The element root should be a pointer to a node too:

typedef struct tree_st {
    int size;
    node *root; 
} tree;

edited Oct 14, 2018 at 7:39

answered Oct 14, 2018 at 7:27

Rabbid76

212k30 gold badges163 silver badges205 bronze badges

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

2 Comments

cellka Over a year ago

I get incompatible types error by t->root = *toInsert;

cellka Over a year ago

Now it works but the error (mentioned above) is still present

Collectives™ on Stack Overflow

Binary Search Tree with pointers in C

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related