malloc in pointer received as argument

Question

I'm implementing an binary search tree but for some reasons I 'm not able to add a node

my: input was :

a.value = 5;
add_bst_node(&t,a); 

mystructures:

typedef struct BST_node{
 entity value;
 struct BST_node* left;
 struct BST_node* right;
}BST_node;

typedef struct BST_tree{
 BST_node* root;
}BST_tree;

my code for add a node:

void add_bst_node2(BST_node* root,entity* e){
 if(!root){
  root = (BST_node*)malloc(sizeof(BST_node));
  root->value = *e;
  root->left = NULL;
  root->right = NULL;
  return;
 }
 else if(great_than(&root->value,e))
  add_bst_node2(root->left,e);
 else
  add_bst_node2(root->right,e);
 }

 void add_bst_node(BST_tree* t,entity e){
  add_bst_node2(t->root,&e);
  printf("%d\n",t->root==NULL);
 }

Someone can explayn why I'can't add a node?

Answer 1

Apart from not passing double pointer to BST_node (i.e. BST_node**) in add_bst_node2() as noted in the comments, you also didn't implement the function properly.

Your implementation never really adds a node, but instead in enters into infinite recursion.

Here you can find some clean theory about BST - http://www.zentut.com/c-tutorial/c-binary-search-tree/

Here is an untested correction of your code. Note that here we pass pointer to BST_tree instead of BST_node

void add_bst_node2(BST_tree* tree,entity* e){
    if(!tree->root){
        /* If the binary search tree is empty, we just create a root node */
        tree->root = bst_create_node(e);
        return;
    }

    int is_left  = 0;
    BST_node* current_node = tree->root;
    BST_node* prev   = NULL;

    /* Traverse the tree until we find the proper position for the new node.
     * The position is denoted by 'current_node'
     */
    while(current_node != NULL) {
        prev = current_node;

        if(greater_than(&current_node->value, e)) {
            is_left = 1;
            current_node = current_node->left;
        } else {
            is_left = 0;
            current_node = current_node->right;
        }
    }

    /* We finally know the position where we should add the new node */
    if(is_left)
        prev->left = bst_create_node(e);
    else
        prev->right = bst_create_node(e);
}

We introduce another function for creating and initializing a node...

BST_node *bst_create_node(entity *e)
{
    BST_node *n = malloc(sizeof(BST_node));

    n->value = *e;
    n->left = NULL;
    n->right = NULL;

    return n;
}

And finally we change add_bst_node()

void add_bst_node(BST_tree* t,entity e){
    add_bst_node2(t, &e);
    printf("%d\n", t->root==NULL);
}