C ++: pointer versus pointer to pointer to insert node into binary tree

Question

I created a function to insert an element into a binary tree and, firstly, I did the following in Visual Studio 2012:

void Insert(Nodo *root, int x){ if(root == NULL){ Nodo *n = new Nodo(); n->value = x root = n; return; } else{ if(root->value > x) Insert(&(root)->left, x); else Insert(&(root)->right, x); } } 

But the same code does not work in Dev-C ++, I need to use a pointer pointer to make it work, for example:

 void Insert(Nodo **root, int x){ if(*root == NULL){ Nodo *n = new Nodo(); n->value = x *root = n; return; } else{ if((*root)->value > x) Insert(&(*root)->left, x); else Insert(&(*root)->right, x); } } 

Does anyone know why this is happening?

Answer 1

The first code should not compile. In fact, it does not compile under MSVC 2013.

Why?

The node structure should look something like this:

 struct Nodo { int value; Nodo*left, *right; // pointer to the children nodes }; 

This means that (root)->left is of type Nodo* . Therefore, &(root)->left is of type Nodo** , which is incompatible with the argument Nodo* .

In any case, in your insert function, you, of course, want to modify the tree. But if you, for example, run: root = n; , you just update the root argument (pointer). This update will be lost as soon as you leave the function. Here, of course, you want to change either the contents of the root node, or rather, a pointer to the root of the node.

In the second version, you pass the address of the pointer to the node as an argument, and then, if necessary, update this pointer (the expected behavior).

Note

The first version can be "saved" if you want to follow the link:

 void Insert(Nodo * &root, int x){ // root then refers to the original pointer if(root == NULL){ // if the original poitner is null... Nodo *n = new Nodo(); n->value = x root = n; // the orginal pointer would be changed via the reference return; } else{ if(root->value > x) Insert(root->left, x); // argument is the pointer that could be updated else Insert(root->right, x); } }