Problem with local pointer

Question

I am studying the binary tree problem and I came up with the following implementation for insertion that works correctly.

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, trying to simplify this function, I tried to allocate * n to the local Node pointer, for example:

 Node * c = *n; 

Then I went through the function and replaced all instances of * n with c. However, the function is not performed properly. Can someone explain to me why this is not working? Thanks.

EDIT: I must indicate that in new changes, the function will exit immediately after the first if statement. This seems to indicate that the pointer passed to the (root) is always NULL, which means that the nodes are not stored properly. I don’t know what is the reason, but I think it is somewhere between the local pointer and the end of the first if statement.

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

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

It is never executed!

Answer 1

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

You might be fine if you do *n = c; before each return (or change the code so that there is only one return, and reassign before). So - untested 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 a test harness. Printing is not great - but at least it works. Note that you need to free the tree using postoperative traversal; printing can be done previously or in order (as here) or after ordering.

 #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 THINK that:

insert (& (* n) → right, data); as well as insert (& c-> to the right, data);

Not the same.

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

Answer 3

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

it should be:

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

(*n) instead of &(*n) in your insert () calls. This is because * n is your Node repeat, you do not (and cannot) take the address * n. If this does not work, send your full code, including. Node -struct.

Answer 4

I really don't understand that I have a double pointer to 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; } 

Everything seems to be working fine on my computer. Will it meet your needs?

Do not be shy if you need clarification.