CODEWITHSUNDEEP
c++data-structuresbinary-search-tree
thoughtful me
thoughtful me

Reputation: 115

Bst- Why did my Bst worked after chaning node* to node*&?

I implemented BST and my implementation looks like this

 void insert(node*&r,int key){      // 1 ) node* r 2) node*&r
    if(r==NULL){
        r=new node(key);
        return;
    }
    c++;
    if(r->key > key){
        insert(r->right,key);
    }
    else if(r->key <key){
        insert(r->left,key);
    }
  }

int main()
{
    int n;
    cin>>n;
    node *root=NULL;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        insert(root,x);
    }
    return 0;
}

I was clear before why node*& not node*.But I have mental blockage today.I am confused that if we use node*& than we will edit the root permanently that is the identity of BST hence we will loose BST.On the other hand I am confused why it doesn't work on using node* .can anyone please explain this in detail.Which one and why ?

Upvotes: 0

Views: 44

Answers (1)

vsoftco
vsoftco

Reputation: 56567

It works now because you pass the pointer by reference, hence the function in which it's passed can modify it. Otherwise you pass the pointer by value, and at the exit from the function, the pointer passed as argument is not modified.

Look what's happening here:

node *root=NULL; // so initially root is nullptr

then, in the for loop, you have

insert(root,x); // better take it by reference, otherwise root is not modified

At the exit from insert, root is modified only if is passed by reference, otherwise, if passed by value, it stays NULL. Just remember that a pointer behaves like any other variable, and in C++ it is passed by value by default.

Upvotes: 1

Related Questions