C binary search tree implementation - insert

Question

I am trying to create a program which which takes a list of words as an input, and sorts them into a binary tree, in order to allow them to be found, e.g. like a dictionary. This is what I have done so far, but am getting a segmentation error with newEl -> el = input; I know this is because it is trying to point to a NULL el, when the tree is first created, but i'm not sure what the best way to improve my code would be. Anyone have any ideas? Thanks.

struct node *tra(struct node * start, Type input) {
  struct node * thisNode = start;

  if (thisNode == NULL)

    Type current = thisNode -> el;

    if (strcmp(input, current) > 0)
        return tra(thisNode -> right, input);

    else if (strcmp(input, current) < 0)
        return tra(thisNode -> left, input);

    else
        return thisNode;
  }
}

Ta insert(Type input, Ta ta) {
  if ((find(input, ta)) == FALSE) {
    newEl -> el = input;

  }

  return ta;
}

Boolean find(Type input, Ta ta) {
    if (tra(ta -> head, input) == NULL)
        return FALSE;
    }

if find() returns false, tra will also return NULL, and the assignment to newEl->XXX will dereference a NULL pointer. Anyway, the most elegant solution involves a pointer-to-pointer. — wildplasser, Feb 17 '13 at 15:45
`struct node *newEl = tra(ta -> head, input);` will either return you an existing item or null. it will never give you a pointer to a new object. — Roee Gavirel, Feb 17 '13 at 15:47
Sorry, I started reading the code. The text came later. (I don't like text ;-) — wildplasser, Feb 17 '13 at 15:48
@wildplasser no problem, just really need the help been struggling for hours :( — user1899174, Feb 17 '13 at 15:50
Seems like you want to create a new node, but I don't see anywhere where you allocate space for a new node (e.g. "newEl = (struct node*)malloc(sizeof(struct node));"). — Ron Burk, Feb 17 '13 at 15:50
Add a new function called "AddNode" which receive the `input`, go over the tree and find the node before the location which the new input should be added. then create a new node and add it there. — Roee Gavirel, Feb 17 '13 at 15:51
Your edit makes no sense. If you cannot dereference newEl, you cannot dereference it. Not once, not twice, not three times. — wildplasser, Feb 17 '13 at 17:03

score 0 · Answer 1 · answered Feb 17 '13 at 15:54

Since you already know what the problem is you should resolve it. Allocate the node and insert it.

Ta insert(Type input, Ta ta) {
  if ((find(input, ta)) == FALSE) {
    // call to tra will fail. this is the place to create a new node
    struct node *newEl = (struct node*)  malloc(sizeof(struct node));
    newEl -> el = input;
    newEl -> left = 0;
    newEl -> right = 0;
    // do the insertion ....
  }
}

score 0 · Answer 2 · answered Feb 17 '13 at 15:58

0

Seems like you want to create a new node, but I don't see anywhere where you allocate space for a new node, like:

newEl = (struct node*)malloc(sizeof(struct node));

Good luck!

answered Feb 17 '13 at 15:58

Ron Burk

6,058
1
18
20

This would still cause newNode to be unreacheable by the caller. BTW: you should not cast malloc()s return value. It is not needed and potentially dangerous. – wildplasser Feb 17 '13 at 16:05
Why would this be dangerous? – dualed Feb 17 '13 at 17:19
@wildplasser you are repeating a meme I violently disagree with; see FAQ. – Ron Burk Feb 17 '13 at 18:32
FAQ , which FAQ, the c.l.c FAQ ? – wildplasser Feb 17 '13 at 18:38
http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc I'm near the bottom :-). – Ron Burk Feb 17 '13 at 18:44

wildplasser · Accepted Answer · 2013-02-17T23:49:41.717

This is a pointer to pointer equivalent:

typedef char *Type;
struct node {
  struct node *left , *right;
  Type payload;
  };    

struct node **find_pp(struct node **pp, Type input) {
  struct node *thisNode ;

  while ( thisNode = *pp ) {
    int diff;
    diff = strcmp(input, thisNode->payload);
    if (!diff) break;
    pp = (diff <0) ? &thisNode->left : &thisNode->right;
  }
return pp;
}

Boolean find(struct node *root, Type thing)
{
  struct node **pp;
  pp = find_pp( &root, thing);
  return (*pp) ? True : False;
}

void insert (struct node **pp, Type thing)
{
  struct node *newNode;
  pp = find_pp (pp, thing);

  if (*pp) return; /* already exists */
  *pp = newNode = malloc (sizeof *newnode);
  newNode->payload = strdup(thing);
  newNode->left = NULL;
  newNode->right = NULL;

return;
}

a few notes:

inserting a node into a tree means: assigning to a pointer that was previously NULL
the empty tree is also a tree: just a pointer (to the root of the tree) that happens to be null
finding a node in a tree means: finding the place ( :=pointer) where is should be (if it existed)
if it does not exists, this pointer is exactly the place where it should be inserted to bring it into existence
drawing a diagram (with paper and pencil) will help.

C binary search tree implementation - insert

3 Answers3

Linked