Insertion function in a random binary tree

Question

I'm having a problem with my insertion function in this binary tree in C++. The nodes are correctly inserted until I need to add again a node to the right or to the left. The function thinks I don't have any nodes to either the left or the right in the case being that I already inserted nodes in those places.

Here is my code:

void insert(string data)
{    
    srand(time(NULL));
    int r;
    node *aux=head;
    node *n=new node(data);
    if (head==NULL)
    {
        head =n;
        return;
    }

    while (aux!=NULL)
    { 
        r=rand()%100;
        if (r>50)
        {
            cout<<"\nRandom is "<<r<<", Therefore we have to go to the right."<<endl;
            aux=aux->right;  
        }
        else
        {   
            cout<<"\nRandom is "<<r<<", Therefore we have to go to the left."<<endl;
            aux=aux->left;
            if (aux!=NULL)
            {
                cout<<aux->getdata()<<endl;
            }
        }
    }

    aux=n;
    cout<<"\nWe insert "<<aux->getdata()<<endl;
}

Welcome to Stack Overflow! Asking strangers to spot errors in your code by inspection is not productive. You should identify (or at least isolate) the problem by using a debugger, and then come back with a more specific question (once you've narrowed it down to a 10-line test-case). — Oliver Charlesworth
the problem is not within the code, it compiles, the problem resides in the insertion I can't figure out how I can make it to detect why when i need to add a 4th node it doesn't know that the first right and left nodes are already in use. — elenfermodelcpp

Samy Arous Samy Arous · Accepted Answer · 2012-06-24T00:22:28

Here's a slight modification of your code:

void insert(string data)
      {    srand(time(NULL));
           int r;
           node *aux=head;
           node *n=new node(data);
           if(head==NULL){
                          head =n;
                          return;
                          }

       while(aux!=NULL) // We could put while(true) here.
       { 
                       r=rand(); // Modulo is a somehow slow operation
                       if((r  & 1 )== 0) // This is much faster. It checks if r is even
                       {  cout<<"\nRandom is "<<r<<", which is even therefore we have to go to the right."<<endl;
                          if ( aux->right == NULL) // We found an empty spot, use it and break
                          {
                              aux->right = n; break;
                          }
                          else // else move to the right child and continue
                          {
                              aux=aux->right;  
                              cout<<aux->getdata()<<endl;
                          }
                       }
                       else
                       {   
                           cout<<"\nRandom is "<<r<<", which is odd Therefore we have to go to the left."<<endl;
                          if ( aux->left == NULL) // We found an empty spot, use it and break
                          {
                              aux->left = n; break;
                          }
                          else // else move to the left child and continue
                          {
                              aux=aux->left;  
                              cout<<aux->getdata()<<endl;
                          }

                       }
       }
       cout<<"\nWe insert "<<n->getdata()<<endl;

  }

THe main reason is that you are misusing aux. Here's an example which I hope will help you identify your mistake:

node * aux = head; // suppose head doesn't have any child node
node * n = new node(data);

aux = aux->left; // Set aux to point on the left child of head
aux = n; // Set aux to point on n

cout << aux == NULL?"Aux is null":"Aux is not null" << endl;
cout << head->left == NULL?"Left is null":"Left is not null" << endl;

This code shoud return:

Aux is not null
Left is null

The reason is that when we assigned n to aux, we simply told aux to point on n instead of pointing on the left node. We didn't assign n to be the left child of head.

You could also solve this issue by declaring aux to be a pointer of a pointer of node.

node * * aux = &head;

Insertion function in a random binary tree

1 Answers