# Binary search tree node insertion

want to insert element in binary tree. what is wrong in this code. I have a structure with data, left and right as self referencing structure and root as a global variable of type structure initialized to NULL.

void insert(struct tree_node *root,int data) { if(root == NULL) { tree_node *new_node = new tree_node(); new_node->left = NULL; new_node->right = NULL; } else if(root->data > data) { insert(root->left,data); } else { insert(root->right,data); } }

## Answers

There are several issues with the code you propose here:

- You never set your global variable "root". Also, a global variable is always a bad thing (especially if you plan to use threads).
- You never link the new entries to the existing structure.
- You never set the new entry data

You should probably try this instead:

struct tree_node *insert(struct tree_node *root, int data) { if(root == NULL) { struct tree_node *new_node = new tree_node(); new_node->data = data; new_node->left = NULL; new_node->right = NULL; return new_node; } else if(root->data > data) { root->left = insert(root->left, data); } else { root->right = insert(root->right, data); } return root; }

which you can call using

root = insert(root, data);

**you have created new_node but doesn't assign it value .so you can't insert a value to it.

##### you can also use non recursive function to insert

void insert_nrec(int m) //for insert in binary tree { node *tmp,*par,*ptr; ptr=root; par=NULL; tmp=NULL; while(ptr!=NULL) { par=ptr; if(m<ptr->data) { ptr=ptr->lchild; } else if(m>ptr->data) { ptr=ptr->rchild; } else { cout<<"duplicate key found::"; return; } } tmp=new node; tmp->data=m; tmp->lchild=NULL; tmp->rchild=NULL; if(par==NULL) { root=tmp; } else if(m<par->data) { par->lchild=tmp; } else { par->rchild=tmp; } }

When do you set root to anything other than NULL?

Once you do, how do you actually change root->left or right?

I'm just going to rewrite @TheRealNeo's nifty 'functional' answer so that you pass it a reference to the root pointer:

void insert(struct tree_node * &root, int data) { if(root == NULL) { struct tree_node *new_node = new tree_node(); new_node->data = data; new_node->left = NULL; new_node->right = NULL; root = new_node; } else if(root->data > data) { insert( root->left, data); } else { insert( root->right, data); } }

which you call using

insert(root, data);

An advantage of this over the functional one, is there's a good chance the compiler will actually do the recursive calls as 'tail recursions', i.e. when inserting left, instead of making a recursive call, the code will simply change the 'root' reference to refer to 'root->left' and jump back up to the start of the function.

The explicitly non-recursive form is not as clear, since it involves some pointer-to-pointer stuff, but it's really not so bad:

void insert(struct tree_node * &root, int data) { struct tree_node **ptrp = &root; while(*ptrp != NULL ){ struct tree_node *np = *ptrp; if( np->data > data ){ ptrp = &np->left; }else{ ptrp = &np->right; } } // new node will be placed at *ptrp, a location // currently containing NULL. struct tree_node *new_node = new tree_node(); new_node->data = data; new_node->left = NULL; new_node->right = NULL; *ptrp = new_node; }