CODEWITHSUNDEEP
c
cellka
cellka

Reputation: 129

Binary Search Tree with pointers in C

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:

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

Upvotes: 2

Views: 608

Answers (1)

Rabbid76
Rabbid76

Reputation: 211258

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;

Upvotes: 1

Related Questions