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
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.
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.
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.
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*.
