Segmentation error while inserting into binary tree

Question

I cannot figure out how to run this correctly, gives segmentation error. A piece of code is below. Can you look at head too , i am not sure if it is right way of initialising head to null in another file , it is run as follows :

Table tb ;
tb= initialise_table (table_size); 
tb = insert(text_words,tb);

//these 3 typedef declarations are in a "some.h" file       
typedef struct node * tree_ptr; 
typedef char* Key_Type; 
typedef struct table* Table;  
struct node { 
    Key_Type element; 
    tree_ptr left; 
    tree_ptr right; 
}; 

struct table { 
    tree_ptr head; 
};

Table init_table()  {

   Table head = NULL;

} 
Table insert(Key_Type key ,Table  temp )  {
    tree_ptr t = (tree_ptr)malloc(sizeof(tree_ptr));
    t->element = key;
    // t->left = t->right = NULL;
    if (temp->head==NULL) {
        temp = (Table)malloc (sizeof (Table)); 
        temp->head = t;
        printf("empty tree ");
    }    
    else {          
        temp = insert(t->element,temp);
        printf("inserted into "); 
    }

    return temp;   
    printf("wowo!");
}

Answer 1

The primary issue is in the code which, you say, is used to invoke the functions:

Table tb;

tb = insert(text_words, tb);

You have an uninitialized pointer, tb, which you pass to the function. Inside the function, you have:

Table insert(Key_Type key, Table temp)
{
    tree_ptr t = (tree_ptr)malloc(sizeof(*t));  // Fixed size
    t->element = key;
    // t->left = t->right = NULL;
    if (temp->head==NULL)
    {

You're therefore accessing (dereferencing) the undefined pointer, and your program is crashing.

You should, I assume, be initializing your table with table_init(), but that function is actually no help whatsoever. It defines and initializes a local variable, but doesn't return anything even though it promises to do so.

Please see Is it a good idea to typedef pointers? The short answer is 'No, it usually isn't a good idea'.

You still have problems even if you fix the calling code like this (a necessary but not sufficient step):

Table tb = NULL;
tb = insert(text_words, tb);

or maybe:

Table tb = init_table();
tb = insert(text_words, tb);

but you need a seriously upgraded version of init_table(), such as:

Table init_table(void)
{
   Table root = malloc(sizeof(*head));
   root->head = NULL;
   return root;
}

Your code in insert() needs to ensure that it does not dereference a null pointer (instead of an indeterminate pointer).

Table insert(Key_Type key, Table root)
{
    tree_ptr t = (tree_ptr)malloc(sizeof(*t));  // Fixed size
    t->element = key;
    t->left = t->right = NULL;
    if (root == NULL)
    {
        root = init_table();
        root->head = t;
    }
    else
    {
        …
    }
    return root;
}

Given the Key_Type is a char * in disguise, you may need to review how you save the keys in the tree structure; you may need to use strdup() to copy the data. It is impossible to say for sure without seeing how you are managing the strings that you pass to the insert() function. It could be OK to just save the pointer if the calling code ensures that a new pointer is passed each time. OTOH, if the same pointer is passed each time, you definitely need to copy the data, and using strdup() is a sensible way of doing that. Note that strdup() is standard on POSIX; it is not part of standard C.

Answer 2

Here's one major problem:

tree_ptr t = (tree_ptr) malloc(sizeof(tree_ptr));

should be:

tree_ptr t = (tree_ptr) malloc(sizeof(struct node));

Your code doesn't actually do any binary search. Indeed, it just infinitely recurses creating new nodes. Try something more like this:

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

typedef struct Node
{ 
  char        *element; 
  struct Node *left; 
  struct Node *right; 

} Node;

typedef struct
{
  Node  *root;
  size_t size;

} Tree;

void  Tree_init(Tree *t);
Node *Tree_insert(Tree *t, const char *key);
void  Tree_insert_r(Node *subtree, Node *n, size_t size);
void  Tree_pre_order_r(Node *subtree);

void Tree_init(Tree *t)
{
  t->root = NULL;
  t->size = 0;
}    

Node *Tree_insert(Tree *t, const char *key)
{
  Node *ret = (Node*) malloc(sizeof(Node));

  if (ret)
  {
    ret->left = ret->right = NULL;

    if ((ret->element = strdup(key)))  /* make a copy of key */
    {
      if (NULL != t->root)
        Tree_insert_r(t->root, ret, t->size);
      else
        t->root = ret;

      ++t->size;
    }
    else
    {
      free(ret);
      ret = NULL;
    }
  }

  return ret;
}

void Tree_insert_r(Node *subtree, Node *n, size_t size)
{
  int cmp = strcmp(n->element, subtree->element);

  if (cmp < 0 || (cmp == 0 && size % 2 == 0))
  {
    if (NULL != subtree->left)
      subtree = subtree->left;
    else
    {
      subtree->left = n;
      return;
    }
  }
  else
  {
    if (NULL != subtree->right)
      subtree = subtree->right;
    else
    {
      subtree->right = n;
      return;
    }    
  }

  Tree_insert_r(subtree, n, size);
}

void Tree_pre_order_r(Node *subtree)
{
  if (NULL == subtree)
    return;

  fprintf(stdout, "'%s'\n", subtree->element);

  Tree_pre_order_r(subtree->left);
  Tree_pre_order_r(subtree->right);
}

int main()
{
  Tree t;

  Tree_init(&t);
  Tree_insert(&t, "Hello");
  Tree_insert(&t, "World!");
  Tree_insert(&t, "etc.");

  Tree_pre_order(t.root);

  return 0;
}