Ad

Segmentation Fault Error - Binary Search Tree In C

- 1 answer

I'm trying to build a binary search tree. Inserting an integer using insert function (only using 1 to 100 for testing) and appending the result to a file using inorder traversal. However, i'm getting a segmentation fault error. Using Visual Studio code on Macbook Pro 2020. Also tested on Codeblocks on Windows - filename.exe stops working and crashes.

#include <stdio.h>
#include <stdlib.h>
    
typedef struct node *BST;
    
struct node {
    int data;
    BST left;
    BST right;
};

BST insert(BST root, int number) {
    BST temp = NULL;
    if (root == NULL) {
        temp = *(BST *)malloc(sizeof(BST));
        temp->left = NULL;
        temp->right = NULL;
        temp->data = number;
        root = temp;
        }
    else if (root->data > number) {
        insert(root->left, number);
    }
    else {
        insert(root->right, number);
    }
    return root;
}

//returning null if number not found and pointer to root if found
BST find(BST root, int number) {
    if (root == NULL) {
        return NULL;
    }
    
    if (root->data > number) {
        find(root->left, number);
    }
    else if (root->data < number) {
        find(root->right, number);
    }
    else (root->data = number);
        return root;
}
    
//printing number to file
void inOrder (BST root, FILE *fp) {
    if (root == NULL) return;
    inOrder(root->left, fp);
    fprintf(fp, "%d", root->data);
    inOrder(root->right, fp);
}

int main() {
    BST root = NULL;
    int n = 100;
    int treeArray[n];
    for (int r = 0; r < n; r++) {
        treeArray[r] = r;
    }
    root = insert(root, treeArray[0]);
    for (int x = 1; x < n; x++) {
        insert(root, treeArray[x]);
    }
    
    FILE *treefile = fopen("print_tree.txt", "w");
    inOrder(root, treefile);
    fclose(treefile);
    return 0;
}
    
Error: /bin/sh: line 1: 44278 Segmentation fault: 11 *file path redacted*

What am I doing wrong here? :(

Ad

Answer

Main problem is with this statement:

temp = *(BST *)malloc(sizeof(BST));

As it was already explained in the other answer clearly, I am going to skip that.

So you can do:

temp = malloc(sizeof (struct node));

OR

// to add : this helps in case the type of temp ever changes,
temp = malloc(sizeof(*temp));

Other minor logical changes:

  • In the find function, there is no need of this else if statement
    // = or == doesn't matter now
    else (root->data = number);
  • In the insert function, you forgot to link the nodes which you insert after your root node. So whenever you perform the inorder traversal, you only get the root node i.e 0 in your case.

Note:

typedef is used to make code more readable, but hiding the pointer using typedef creates confusion. So I would suggest not to typedef pointers.

Ad
source: stackoverflow.com
Ad