c++ pointers and pointer to a reference

Question

Im trying to create a Binary search tree. I've used recursive procedures to insert nodes into the tree. The code is as follows.

void BST :: insertRoot(Node* node, int data)    {
    if (node == NULL)
        this -> root = new Node(data);
    else
        insertOthers(node, data);
}
void BST :: insertOthers(Node* node, int data)  {
    if(node == NULL)    {
            node = new Node(data);
            return;
    }
    if(data < node->getData())
        insertOthers(node->getLeft(), data);
    else
        insertOthers(node->getRight(), data);
}

In this code only one node is inserted into the tree and then the connection is broken. However i when I change my Node* to Node*& it works perfectly. Still i cant understand whats the difference between these two. Can anyone explain the differentiation between these two with their memory mapping? Thank you

You have the same problem as another question [I answered recently](http://stackoverflow.com/a/27452472/10077). Big difference is that was C, this is C++. So one way (probably not the best) is to pass a reference to the pointer, as you did with `Node*&`. — Fred Larson, Dec 15 '14 at 15:36
`Node*` is a separate pointer value, independent of all other variables. `Node*&` is a reference to another pointer somewhere else; changing it to point to another object for example will also alter the referent. — cdhowie, Dec 15 '14 at 15:37

score 3 · Accepted Answer · answered Dec 15 '14 at 15:38

If you take the pointer parameter by value:

Node* node

then modifying it:

node = new Node(data);

will change the local variable within the function; but not the caller's argument. This new value will be lost, and the tree will remain as it was.

Passing by reference (that's a reference to a pointer, not a pointer to a reference):

Node*& node

means that the local parameter refers to the same pointer as the caller's argument, so the caller will see that change to the new value. So, assuming the rest of the logic is correct, this will update a pointer within the tree to point to the new node, as you want.

Codor · Answer 2 · 2014-12-15T15:54:44.380

0

The notation Node* means 'pointer to Node', the second one Node*& means 'reference to pointer to Node'. The difference ist that the first one gives you a copy of the address and does not permit to change the pointer in-place such that an effect is visible for the caller.

edited Dec 15 '14 at 15:54

answered Dec 15 '14 at 15:38

Codor

17,447
9
29
56

1

I think it would be a bit easier to follow if `Node*&` was worded "reference to pointer to `Node`." – cdhowie Dec 15 '14 at 15:38
I have changed it; the topic is indeed a bit fiddlish (if that is a word) where confusion is to be expected. – Codor Dec 15 '14 at 15:55

score 0 · Answer 3 · answered Dec 15 '14 at 15:41

When you pass a pointer by value, the function receives a copy of the pointer as the parameter. You cannot modify the original pointer within the function because you only have access to the copy.

When you pass a pointer by reference, the original pointer can be modified through the reference. Which appears to be your intention since otherwise you would leak the allocated node.

It may opinion based, but for better readability, I would declare your function like this: Node* BST::insertOthers(int data) and return the pointer to the allocated node.

score 0 · Answer 4 · answered Dec 15 '14 at 15:54

A pointer is an integral value. When you pass anything by value, an int, double, float, a pointer, etc., the function will be working on a copy. Changes to the copy are not relayed back to the caller.

In short, your problem is no different than this:

void foo(int x)
{
   x = 10;
}

int main()
{
   int value = 0;
   foo(value);
   // value is still 0 after the call, not 10
}

Note that value has not changed, even though it was passed to foo. To fix the problem of having the changes reflect back to the caller, in C++ you pass a reference -- in the above case, a reference to int, in your case, a reference to a Node*.

c++ pointers and pointer to a reference

4 Answers4

Linked