How to use pointers in inserting new node to binary tree when I have in my header struct:

typedef struct bst_node {
  char key;               
  int value;         
  struct bst_node *left; 
  struct bst_node *right; 
} bst_node_t;

How to allocate memory when I use double pointer in void parameters? When I try to run this in tests I get segfault

void bst_insert(bst_node_t **tree, char key, int value) {
  if(tree == NULL){
    tree = malloc(sizeof(struct bst_node));
    (*tree)->key = key;
    (*tree)->value = value;
    (*tree)->right = NULL;
    (*tree)->left =NULL;
  }
  else if(key == (*tree)->key){
    (*tree)->value = value;
  }
  else if((*tree)->key > key){
    bst_insert(&(*tree)->left, key, value);
  }else{
    bst_insert(&(*tree)->right, key, value);
  }
}

CodePudding user response：

Your function takes a pointer to a pointer to a bst_node_t. If bst_insert receives a bst_node_t **tree that is NULL, then there is nothing that function can do, because it cannot access the tree.

void bst_insert(bst_node_t **tree, char key, int value) {
  if(tree == NULL){
    return; //There is nothing to be done.

On the other hand, if the pointer that tree points to is NULL, then we have a valid reference to a tree structure that is empty, so we can allocate memory and store it at the memory location that tree points to:

  if(*tree == NULL){
    *tree = malloc(sizeof(struct bst_node)); //What if malloc fails?
    (*tree)->key = key;
    (*tree)->value = value;
    (*tree)->right = NULL;
    (*tree)->left =NULL;
  }

The line in your original program that says tree = malloc(... is not only not what you want, it is a memory leak, because when bst_insert returns, that value will be lost and you will have no way to free the memory.

Since it is possible for this function to fail, like if you were to call bst_insert(NULL, 0, 0); it may be wise to change the return type from void to int so that bst_insert can communicate to its caller that it was unable to do its job.