bst insert recursion c++

Question

I have a bst encapsulated in a class with a nested node.

When I try to insert and then print tree, the root attribute of the class does not seem to be updated, even though I do update it.

void bst::insert(int key,node* temp)
{
  if(temp==NULL)
  {
      node* ptr=getnewnode(key);
      if(root==NULL)
        root=ptr;
       else
       {
         temp=ptr;
         return ;
       }
  }
     if(key<temp->key)
      insert(key,temp->left);
     if(key>temp->key)
      insert(key,temp->right);
}

class bst
{
typedef struct node
{
int key;
node* left;
node* right;
}node;
node* root; 
void insert(int key,node* temp);
public:
inline void _insert(int key){insert(key,root);}   
};

When i insert say 22,11,33 and then print it, it just shows 22, always the root node.

Answer 1

I suppose that when you call insert() from outside the class, NULL is provided as second argument, because root is private.

Problem 1:

If you insert(22, NULL) the first node is added to your bst as foolows:

  ... 
     if(root==NULL)   // yes, the bst is still empty:  
        root=ptr;     // so root is set to the new node that was created
     else {...}       // and this bloc is ignored 
  }
  if(key<temp->key)   // OUCH !!!! temp is not initalized here                        
  ...                 

You risk here a memory corruption or a segfault !

Problem 2:

If you subsequently insert(11, NULL) here is what happens:

  ... 
      if(root==NULL)   // No, the bst has already a root  
      else {           // so the else block is executed
          temp = ptr;  // you prepare to do something with temp
          return;      // WHY ??  You end the function an return without having done anything 
  ...  

Problem 3:

Suppose you remove the return statement, then remember that you just overwrote temp. The code would continue as follows:

 if(key<temp->key)     // this is false, because temp points to the new node, which has the seme key (temp->key==key) !
 if(key>temp->key)     // this is false, for the same reason 

So none of the recursive insert is done !

Solution:

I'd propose you something like this:

void bst::insert(int key,node* temp)
{
    if(temp==NULL) {
       if(root==NULL) {
           root=getnewnode(key);
           return; 
       }
       else 
           temp=root;  // we now start browsing the tree with root 
    }
    if(key<temp->key) {
        if (temp->left==NULL) 
           temp->left = getnewnode(key);  
       else insert(key,temp->left);
    }
    else if(key>temp->key) {
        if (temp->right==NULL) 
           temp->right = getnewnode(key);
       else insert(key,temp->right);
    }
    else if (key==temp->key) { 
        // to do:  what happens if key==temp->key 
    }
}

It's not clear what is expected when an existing key is inserted again. Up to you to adapt according to your expectations.

Edit: Solution with a wrapper:

Following your edit about using a wrapper I propose you following variant:

void bst::insert(int key,node*& temp)  // attention:  change of signature !!!
{
    if(temp==NULL) {  // either root is null or we have reached a null leave
       temp = getnewnode(key);    // temp is a reference to original root or node pointer.  It can be changed directly with this statement 
       }
    else if(key<temp->key) 
       insert(key,temp->left);
    else if(key>temp->key) 
       insert(key,temp->right);
    else if (key==temp->key) { 
        // to do:  what happens if key==temp->key 
    }
}

Answer 2

I am still not sure what I was doing wrong here but now the code works with the below changes. //wrapper function

void insert(int key)
{
   node * temp=_insert(key,root);
   preorder(root);
}

node* bst::insert(int key,node* temp)
{
 if(root==NULL)
  {
      node* ptr=getnewnode(key);
        root=ptr;
        return root;
  }
   if(temp==NULL)
  {
       node* ptr=getnewnode(key);
       return ptr;
  }
     if(key<temp->key)
      temp->left=insert(key,temp->left);
     if(key>temp->key)
      temp->right=insert(key,temp->right);
}