Local pointer problem

Question

I'm studying a binary tree problem and I have come up with the following implementation for insert which works properly.

int insert(Node ** n, int data) {

  // create new node
  if (*n == NULL) {
    *n = (Node*) malloc(sizeof(Node));
    (*n)->data = data;
    (*n)->left = NULL;
    (*n)->right = NULL;
    return 1;
  }

  else if (data > (*n)->data) {
    insert(&(*n)->right, data);
  }

  else  {
    insert(&(*n)->left, data);
  }

  return 0;
}

But then in an attempt to simplify this function, I tried allocating *n to a local Node pointer like:

Node * c = *n;

I then went through the function and replaced all instances of *n with c. However, the function does not execute properly. Could anyone explain to me why this doesn't work? Thanks.

EDIT: I should point out that in the new changes, the function will immediately exit after the first if-statement. This seems to indicate that the pointer being passed in (the root) is always NULL, which means that the nodes aren't being saved properly. Not sure what the reason is but I think it's somewhere between the local pointer and the end of the first if-statement.

EDIT2: I placed this following check at the end of the first if-block:

if (*n != NULL) printf("Node has been allocated\n");

It never executes!

Answer 1

Your problem is that you made 'c' into a local variable, and edited its contents, but you need to edit the non-local variable.

You might be OK if you do *n = c; before each return (or modify the code so there's only one return, and do the reassignment before that). So - unverified code:

int insert(Node ** n, int data) {

  Node *c = *n;
  int rc = 0;

  // create new node
  if (c == NULL) {
    c = (Node*) malloc(sizeof(Node));
    c->data = data;
    c->left = NULL;
    c->right = NULL;
    rc = 1;
  }
  else if (data > c->data) {
    rc = insert(&c->right, data);
  }
  else  {
    rc = insert(&c->left, data);
  }

  *n = c;
  return rc;
}

Verified code

With test harness. The printing is not magnificent - but it at least works. Note that you need to release the tree using a post-order traversal; printing can be done pre-order, or in-order (as here) or post-order.

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

typedef struct Node Node;
struct Node
{
    int    data;
    Node    *left;
    Node    *right;
};

static void insert(Node **n, int data)
{
    Node *c = *n;

    if (c == NULL)
    {
        // create new node
        c = (Node*) malloc(sizeof(Node));
        c->data = data;
        c->left = NULL;
        c->right = NULL;
    }
    else if (data > c->data)
        insert(&c->right, data);
    else 
        insert(&c->left, data);

    *n = c;
}

static void dumptree(Node **tree, const char *tag)
{
    assert(tree != 0);
    Node *node = *tree;
    if (node != 0)
    {
        dumptree(&node->left, "left");
        printf("data: %d (%s)\n", node->data, tag);
        dumptree(&node->right, "right");
    }
}

static void dump(Node **tree, const char *tag)
{
    printf("In-Order Dump (%s)\n", tag);
    dumptree(tree, "root");
}

static void freetree(Node **tree)
{
    assert(tree != 0);
    Node *node = *tree;
    if (node != 0)
    {
        freetree(&node->left);
        freetree(&node->right);
        free(node);
        //*tree = 0;
    }
}

int main(void)
{
    Node *base = 0;
    int array[] = { 3, 9, 1, 4, 8, 2, 5, 7, 0, 6 };
    int i;

    for (i = 0; i < 10; i++)
    {
        char buffer[32];
        sprintf(buffer, "Add node %d", array[i]);
        insert(&base, array[i]);
        dump(&base, buffer);
    }

    freetree(&base);
    return 0;
}

Answer 2

I don't really get the point of having a double pointer for a tree. Here is another suggestion:

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

struct tree; //forward declaration

struct tree {
    int data;
    struct tree * right;
    struct tree * left;
};

typedef struct tree Node;

Node* insert(Node * n, int data) {

    // create new node
    if (n == NULL) { //We are at the first node
        //It is of no use to create a malloc on n since the value will not be updated in the previous calling function since n is NULL. So we would have to return it
        Node * n = (Node*) malloc(sizeof(Node));
        n->data = data;
        n->left = NULL;
        n->right = NULL;
        return n;
    } else {
        //n is not NULL
        if (data > n->data) {
            if(n->right != NULL) {
                //We have to do recursion
                insert(n->right, data); // n->right is a pointer, type Node*
            } else {
                //We don't want to send a NULL in the recursive call, cause it wouldn't update
                n->right = (Node*) malloc(sizeof(Node));
                n->right->data = data;
                n->right->right = NULL;
                n->right->left = NULL;
            }
        } else  {
            if(n->left != NULL) {
                //We have to do recursion
                insert(n->left, data); // n->right is a pointer, type Node*
            } else {
                //We don't want to send a NULL in the recursive call, cause it wouldn't update
                n->left = (Node*) malloc(sizeof(Node));
                n->left->data = data;
                n->left->right = NULL;
                n->left->left = NULL;
            }
        }

        return NULL;
    }
}

int main(void) {
    Node * root = NULL;

    root = insert(root, 10); //First call to initialise the root
    insert(root, 11);

    printf("%d \n", root->data);

    return 0;
}

It seems to run fine on my computer so far. Would it answer your needs?

Feel free if you need precisions.

Answer 3

insert(&(*n)->right, data);

should be:

insert((*n)->right, data);

(*n) instead of &(*n) in both your insert()-calls. This is because *n is your Node-pointer, you dont need to (and cannot) take the address of *n. If this doesnt work, please post your complete code incl. Node-struct.

Answer 4

I THINK that:

insert(&(*n)->right, data); and insert(&c->right, data);

is not the same.

c is a different place in the memory than &(*n).