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);

as shown on this codepad


**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;
}

Need Your Help

Autocomplete - user typing too fast - select typed input

javascript php jquery ajax autocomplete

I have the following code for multiple autocomplete of various fields. All works fine, but the problem is that my useres type too fast and ajax do not have time to load all results. Therefore, when

How do I hide a file inside an image with Python?

python image file security steganography

I know it's possible in Batch using the 'copy' command with the '/B' switch, i.e.: