"&" operator in c++ template function definitions

Question

I am writing a template BST class and notice that I need to declare the "insert" parameters like this:

void BST<TYPE>::insert(TYPE iData, int line, node *&n)

instead of:

void BST<TYPE>::insert(TYPE iData, int line, node *n)

The only difference being the "&" for passing the node pointer. The full code for the function is:

template <class TYPE>
void BST<TYPE>::insert(TYPE iData, int line, node *&n){
    if(n == NULL){
        n = new node(iData, line, NULL, NULL, NULL);
    }
    else if(iData < n->data){
        insert(iData, line, n->leftChild);
    }
    else if(iData > n->data){
        insert(iData, line, n->rightChild);
    }
    else if(iData == n->data){
        while(n->head != NULL){ //traverse to end of list
            n = n->head;
        }
        n->head = new node(iData, line, NULL, NULL, NULL); //add p to end of list
    }
}

The tree holds duplicates, which is why there is an else if(iData == n->data).

My thought was that if we pass a pointer to a child, then eventually when NULL is found, when we create a new node, it will be at the address in memory pointed to by either the leftChild or rightChild pointer. Instead, it seems that if we don't add the & operator, the new node is created but is not "connected" to the tree.

I'm wondering if someone could explain the syntax here. Also, I apologize for any breaches of ettiquette; this is my first post on SO. This BST is for a homework assignment, but the question I've asked is not. It's just something I'm curious about.

Thanks.

Answer 1

When you have a function parameter int& i, any changes to i inside the function, also change the variable passed to the function. When the parameter is int i, a copy is made inside the function, and any changes to the parameter do not affect the variable passed to the function.

There's no reason the same logic cannot be applied to pointer parameters. When you have node *n, a copy of the pointer is made, and if the pointer inside the function is made to point to something else, the pointer that was passed to the function from outside is not changed. When the parameter is node *&n, if the parameter is made to point to something else inside the function, the pointer variable outside the function which was passed in, is also changed to point to the same thing.

I didn't look too much at the function, but I assume the logic requires this function to update the pointer outside the function call too.