How do I remove this segmentation fault in my bst_insert_node function?

Question

I am having a segmentation fault in my function bst_insert_node(). Left is the left "child" of the node which always has a smaller phone value than it's parent. Right is the right "child" of the node which always has a greater phone value than it's parent. Bst stands for binary search tree. My main function is inside another file. The main problem should be my function bst_insert_node().

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "introprog_telefonbuch.h"

// Adds a node with the given phone number (phone) and the name of the owner of that phone number
// into the binary search tree.

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {

bst_node* new = malloc(sizeof(bst_node));
name = malloc(sizeof(char) *MAX_STR);
snprintf(name, MAX_STR, "%s",name);
new->left = NULL;
new->right = NULL;
new->parent = NULL;
new->phone = phone;

if(bst == NULL){
bst->root = new;
}

bst_node* finder = bst->root;

while(finder != NULL){
if(finder->phone == phone){
  printf("This phone number already exist");
  return;
}
if(phone < finder->phone){
  if(finder->left == NULL){
    new->parent = finder;
    finder->left = new;
    return;
  }
  finder = finder->left;
}


if(phone > finder->phone){
  if(finder->right == NULL){
    new->parent = finder;
    finder->right = new;
    return;
  }

  finder = finder->right;
}
}
}

// This function returns a pointer that points to the node that contains the phone
// number that is being searched. If such a phone number is non existent,
// you return NULL.
bst_node* find_node(bstree* bst, unsigned long phone) {

bst_node* finder = bst->root;

while(finder != NULL){                       

if(finder->phone == phone){ 
    return finder;
}

if(finder->phone > phone){
    finder = finder->left;
}  
else{
    finder = finder->right;
} 

 }
  return NULL;
}

// print a sub-tree in "in-order" order
void bst_in_order_walk_node(bst_node* node) {

if (node == NULL){
return;
}

else{
bst_in_order_walk_node(node->left);
print_node(node);
bst_in_order_walk_node(node->right);
}
}

// the same as bst_in_order_walk_node just that you do it for the whole tree.
void bst_in_order_walk(bstree* bst) {
    if (bst != NULL) {
        bst_in_order_walk_node(bst->root);
}
}

// deletes the all sub-tree of node
void bst_free_subtree(bst_node* node) {
    if(node == NULL){
        return;
 }
 else{
    bst_free_subtree(node->left);
    bst_free_subtree(node->right);
    free(node->name);
    free(node);
 }
 }

 // Deletes the whole tree
 void bst_free_tree(bstree* bst) {
    if(bst != NULL && bst->root != NULL) {
        bst_free_subtree(bst->root);
        bst->root = NULL;
}
}

Here's the the main and interface function:

// Kreiert eine Benutzeroberfläche
bstree* interface(bstree *bst) {
    help();
    char *operation;
    unsigned long phone;
    char *name;
    read_line_context in;
    open_stdin(&in);
    printf("> ");
    while (read_line(&in, &operation, &phone, &name) == 0) {
        if (operation != NULL) {
            if (operation[0] == '?' && phone > 0) {
                find_and_print(bst, phone);
            } else if (operation[0] == '+' && phone > 0 && strlen(name) > 0) {    
                bst_insert_node(bst, phone, name);
            } else if (operation[0] == 'd') {
                debug(bst);
            } else if (operation[0] == 'p') {
                bst_in_order_walk(bst);
            } else if (operation[0] == 'q') {
                break;
            } else {
                printf("Inkorrekte Eingabe\n\n");
                help();
            }
        }
        printf("> ");
        phone = -1;
    }
    printf("Exiting...\n");
    close_file(&in);
    return bst;
    }

int main(int argc, char** argv) {
    // Create an empty search tree
    bstree bst;
    bst.root = NULL;
    bst.count = 0;

    if (argc != 2)
    {
        printf("Nutzung: %s <Dateiname>\n",argv[0]);
        return 1;
    }

    // reading the txt file
    read_file(argv[1], &bst);

    // creating the interface
    interface(&bst);

    bst_free_tree(&bst);

    return 0;
    }

The program is supposed to take a text file which contains all of the phone numbers and the names and put it into a binary search tree. My program is compiling, but for some reason when I press "p" (pressing p should show you the "in-order" sorted phone numbers), no phone numbers show up and the program just waits for another input again.

Also, it could be good to understand what happens with name = malloc(sizeof(char) *MAX_STR) directly followed by snprintf(name, MAX_STR, "%s",name). The latter which is explicitly undefined behavior by the way. — Some programmer dude
Possible duplicate of Definitive List of Common Reasons for Segmentation Faults — Brian Tompsett - 汤莱恩
Also, don't allocate a new node until you reach the leaf where it should have been. Then, when you do allocate it, return it so that it can be linked into the tree by assigning the result to left or right in the parent. — 500 - Internal Server Error

Reticulated Spline Reticulated Spline · Accepted Answer · 2018-12-26T19:59:19

One possible segfault is here:

if(bst == NULL){
    bst->root = new;
}

You can't assign anything to members of bst as it's null. Perhaps you meant to construct a new BST here? A few other notes...

Personally, I would avoid using the token new as it's going to confuse C++ programmers.
The result of malloc should be checked in case it fails, but more importantly snprintf() shouldn't be writing to the buffer it's reading from.

How do I remove this segmentation fault in my bst_insert_node function?

1 Answers