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.

The only side effect of your code (besides leaking memory) is changing root exactly once, from NULL to the return value of the very first getnewnode call. Everything else is a very elaborate no-op. — Igor Tandetnik
– Igor Tandetnik, Commented Dec 21, 2014 at 18:15
What effect does temp=ptr have before the return in that else clause? What type is node? — Brian Cain
– Brian Cain, Commented Dec 21, 2014 at 18:16
temp=ptr, i am assuming means root->right = new node in case of 2nd node addition..root->right comes from the call insert(key,temp->right) — basav
– basav, Commented Dec 21, 2014 at 18:37

Christophe · Accepted Answer · 2014-12-21 19:30:12Z

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

edited Dec 21, 2014 at 19:30

answered Dec 21, 2014 at 18:46

Christophe

75.1k7 gold badges87 silver badges182 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

basav Over a year ago

second point -- Only teh first time insert(12,null) is called because root is null....then onwards, the call is always insert(xyz,root) and root is non null

Christophe Over a year ago

@basav: I've completed the post with my assumptions. Outside the bst, people cannot provide root because it's a private member, so I expected, that NULL would be the default value when the function is called from oustide. If it's not the case and if you have a front-end member function that calls insert() by providing it root, just let me know and show the corresponding code.

basav Over a year ago

Yes, I have a wrapper function in public taht calls the private method.I have edited the code now accordingly.

Christophe Over a year ago

I recommend you to get rid of the wrapper, add a default parameter to your existing function in the class as follows: public: void insert(int key,node* temp=NULL); and use the code above. From outside you could then call insert(22), without additional code.

basav Over a year ago

That is a nice alternative, i will try it out.thanks.

|

basav · Accepted Answer · 2014-12-21 19:23:38Z

0

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

answered Dec 21, 2014 at 19:23

basav

1,49513 silver badges20 bronze badges

Collectives™ on Stack Overflow

bst insert recursion c++

2 Answers 2

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related