insert into binary tree question..

i wrote a function called insert i want to build a binary tree like this

Code:

    2
   / \
  1   10
     /
    5

for that i wrote a function as i read in the tutorials
i cant see where is my mistake in that function

Code:

#include <stdio.h>

typedef struct node{
  struct  node *left;
   struct node *right;
    int data;

}node;
node  insert (node *root,int data);

int main(){

node * root;
root=insert(root,2);
root=insert(root,1);
root=insert(root,10);
root=insert(root,5);
    return 0;
}

node  * insert (node *root,int data){
 if (!root){
     root=malloc(node);
     root->data=data;
     return root;
 }//end if

 else{
     if (data=<root->data){ //start if check
         return insert(root->left,data);
     }//end if check
     else {
         return insert(root->left,data);
     }

 }//end else
}//end insert

You may want to set root to NULL when you declare the variable.

Also, as you insert, you may want to set the left/right pointers to NULL.

--
Mats

1. Code:

   node * root  = NULL;

2. Code:

   data=<root->data

   doesn't mean anything. Presumably you don't want the equal sign.
3. You need to make sure that in your left/right cases that you set the link -- you don't want to return the inserted thing, you want to set root->left to the value of the inserted thing. Then after that you need to return root.

regarding the second one:

Code:

data=<root->data

the data on the left side is a parameter in the input of the insert function.
the data on the right side is the data inside the node.
so its comparing the data in the root with the data parameter and inserts it to the left
if its smaller or equals
and to the right if the data parameter is bigger then the data in the root

so in the end i add the line
return root;

is that ok?

Code:

#include <stdio.h>

typedef struct node{
  struct  node *left;
   struct node *right;
    int data;

}node;
node  insert (node *root,int data);

int main(){

node * root=NULL;
root=insert(root,2);
root=insert(root,1);
root=insert(root,10);
root=insert(root,5);
    return 0;
}

node  * insert (node *root,int data){
 if (!root){
     root=malloc(node);
     root->data=data;
     return root;
 }//end if

 else{
     if (data=<root->data){ //start if check
         return insert(root->left,data);
     }//end if check
     else {
         return insert(root->left,data);
     }

 }//end else

return root;  //always return the root of the tree
}//end insert

>> root=malloc(node);

That doesn't even compile. Pay attention to your compiler errors.

>> so its comparing the data in the root with the data parameter

Reread tabstops post. It's *NOT* valid C.

>> is that ok?

If you're not even going to listen to the advise posted, then why bother?

Originally Posted by transgalactic2

regarding the second one:

Code:

data=<root->data

the data on the left side is a parameter in the input of the insert function.
the data on the right side is the data inside the node.
so its comparing the data in the root with the data parameter and inserts it to the left
if its smaller or equals
and to the right if the data parameter is bigger then the data in the root

If you think =< means anything in C, there's nothing I can do for you. Look up your comparison operators again.

Originally Posted by transgalactic2

so in the end i add the line
return root;

is that ok?

If you had fixed the other stuff, yes. Since you didn't, not quite.

Originally Posted by transgalactic2

Code:

#include <stdio.h>

typedef struct node{
  struct  node *left;
   struct node *right;
    int data;

}node;
node  insert (node *root,int data);

int main(){

node * root=NULL;
root=insert(root,2);
root=insert(root,1);
root=insert(root,10);
root=insert(root,5);
    return 0;
}

node  * insert (node *root,int data){
 if (!root){
     root=malloc(node); 
     root->data=data;
     return root;
 }//end if  /*Other people have told you how to fix this. */

 else{
     if (data=<root->data){ //start if check
         return insert(root->left,data); /*You cannot RETURN here; you must set the link here*/
     }//end if check
     else {
         return insert(root->left,data);  /* ditto */
     }

 }//end else

return root;  //always return the root of the tree
}//end insert

why this line is not correct?
i assign space into the empty node.

Code:

root=malloc(node);

malloc does not take a type -- it takes a number of bytes. You must not give it a type; you must give it a number of bytes.

If nothing else, do a board search on malloc and look at the 17304 (approximately) examples of it being correctly used.

ahhh like this

Code:

root=malloc(sizeof(node));

regarding this error:

Code:

return insert(root->left,data); /*You cannot RETURN here; you must set the link here*/

i send the data to the left side of the tree
we need to return a linked node
and thats what the function does in the end
where am i mistaken?

Code:

#include <stdio.h>

typedef struct node{
  struct  node *left;
   struct node *right;
    int data;

}node;
node  insert (node *root,int data);

int main(){

node * root=NULL;
root=insert(root,2);
root=insert(root,1);
root=insert(root,10);
root=insert(root,5);
    return 0;
}

node  * insert (node root,int data){
 if (!root){
     root=malloc(sizeof(node));
     root->data=data;
     
 }//end if

 else{
     if (data<=root->data){ //start if check
         return insert(root->left,data);
     }//end if check
     else {
         return insert(root->right,data);
     }

 }//end else
return *root;
}//end insert

i did the linking you said
i think you meant that

it still doesnt work

Code:

#include <stdio.h>

typedef struct node{
  struct  node *left;
   struct node *right;
    int data;

}node;
node  insert (node *root,int data);

int main(){

node * root=NULL;
root=insert(root,2);
root=insert(root,1);
root=insert(root,10);
root=insert(root,5);
    return 0;
}

node  * insert (node root,int data){
 if (!root){
     root=malloc(sizeof(node));
     root->data=data;

 }//end if

 else{
     if (data<=root->data){ //start if check
         return root->left=insert(root->left,data);
     }//end if check
     else {
         return root->right=insert(root->right,data);
     }

 }//end else
      return *root;
}//end insert

You absolutely can't return *root at the end of the code.

I'm sure you should return the root node at all times when you return from the function.

You still need to set the new node's left/right pointers to NULL when you add a node, and when you have added the node, the left or right node of the node where you added the new node needs to be modified.

--
Mats

#1. Mismatch in return type of function and first function argument in declaration/definition:

Code:

node  insert (node *root,int data);

node  * insert (node root,int data){
   ...
}

That a typo?

#2. Already mentioned by matsp, but you need to set the left/right pointers to NULL after you malloc the memory:

Code:

 if (!root){
    root=malloc(sizeof(node));
    root->data=data;
    root->left = NULL;
    root->right = NULL;
 }

#3. Setting of the current root's left/right pointers to the returned value of the recursive calls.

Code:

else{
     if (data <= root->data){
         root->left = insert(root->left,data);
     }
     else {
         root->right = insert(root->right,data);
     }

 }

#4. Bad return type (don't need that *).

Code:

return *root;

Why do you insist on using the word return there? You do not want to return (you're going to return root -- not *root! -- later), so don't return.