csegmentation-faultbinary-search-tree

Segmentation fault while implementing a binary tree in c


I am new to c, but for a project I am implementing a binary tree. here is my code for the functions:

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

typedef struct BSTnode{
  int key;
  int subtree_size;
  struct BSTnode* left;
  struct BSTnode* right;
} TreeNode;

TreeNode* newNode(int value){
  TreeNode *node = malloc(sizeof(TreeNode));
  node->key = value;
  node->left = NULL;
  node->right = NULL;
  node->subtree_size = 1;
  return node;
}

TreeNode* insert(TreeNode* root, TreeNode* to_insert){
  if(root == NULL){
    root = newNode(to_insert->key);
  }
  else if(to_insert->key> root->key){
    if(root->right == NULL){
      root->right = to_insert;
      return root;
    }
    else{
      root->right = insert(root->right, to_insert);
    }
  }
  else if(to_insert->key< root->key){
    if(root->left == NULL){
      root->left = to_insert;
      return root;
    }
    root->left = insert(root->left, to_insert);

  }

  root->subtree_size = 1 + (root->left? root->left->subtree_size: 0) + (root->right? root->right->subtree_size: 0);
  return root;
}

int find(TreeNode* root, int value){
  if(root == NULL || root->key == value){
    return root->key;
  }
  else if(value > root->key){
    return find(root->right, value);
  }
  else{
    return find(root->left, value);
  }
}

In my main function, I am reading from a file that contaqins a number on each line that I have to insert into the BST. Each line starts with a letter followed by the number seperated by the space.

int main (int argc, char* argv[]){
  FILE* input;

  input = fopen(argv[1], "r");

  char oper;
  int num;

  TreeNode* root = NULL;
  
  while(fscanf(input, "%c", &oper) != EOF){
    if(oper == 'i'){
      fscanf(input, " %d\n", &num);
      TreeNode* to_insert = newNode(num);
      insert(root, to_insert);
      //printf("operation: %c, num: %d\n", oper, num);
    }
    if(oper == 'r'){
//do some other thing
    }
  }
  if(root == NULL){
    printf("yes\n");
  }
  printf("size: %d\n", root->subtree_size);
  printf("left size: %d\n", root->left->subtree_size);
  printf("right size: %d\n", root->right->subtree_size);
  fclose(input);
}

Running the code prints "yes" then it gives me a seg fault. I have seen another post about a similar problem and the solution was to change the insert function to take in a double pointer for root. Does that work here? Id so, what would it look like? I am not really good with double pointers.

Edit 1: assume fscanf() and the input file are properly used and opened.

Edit2: the input file would look like this:

i 10
i 20
i 30
i 40
i 50
i 60
i 70
i 80
i 90
i 99
i 15
i 14
i 12
i 25
i 28
i 95
i 35
i 38
i 11
i 23
i 22

Solution

  • Your problem:

    Your insert() function returns root. But you never assign the return value to anything, at least not in your main():

    TreeNode* root = NULL;
    
    while(fscanf(input, "%c", &oper) != EOF){
      // ...
      insert(root, to_insert);
    

    Your root always stays NULL.

    How I found out:

    gcc -Wall -Wextra -g testme.c -o testme
    gdb -tui --args ./testme input.txt
    break main
    run
    

    And then "n" for next (step over) and "s" for step (step in). Either learn to use gdb from there, or familiarize yourself with a different debugger of your choosing. Doing software development without a debugger is hard. Don't try it.

    My fix:

    I abhor double pointers. Luckily, there's a simple fix to your problem. In insert(), for the first node received, don't newNode(), just take the node you're given:

    if(root == NULL){
      root = to_insert;
    }
    

    And in main(), assign the return value to root:

      TreeNode* to_insert = newNode(num);
      root = insert(root, to_insert);
    

    Yet to do:

    Note that your program leaks all the memory it allocated.

    You need to check root for NULL before accessing root->left and root->right (in case you didn't read any data), and you need to check either of those for NULL again before accessing their respective ...->subtree_size (in case you, as with your example data, have no data at all in one subtree).