Why is pointer-to-pointer being used in this prog ?

Question

The following program shows how to build a binary tree in a C program. It uses dynamic memory allocation, pointers and recursion. A binary tree is a very useful data-structure, since it allows efficient insertion, searching and deletion in a sorted list. As such a tree is essentially a recursively defined structure, recursive programming is the natural and efficient way to handle it.

tree
   empty
   node left-branch right-branch

left-branch
   tree

right-branch
   tree

Here's the code:

#include <stdlib.h>
#include <stdio.h>

struct tree_el {
   int val;
   struct tree_el * right, * left;
};

typedef struct tree_el node;

void insert(node ** tree, node * item) {
   if(!(*tree)) {
      *tree = item;
      return;
   }
   if(item->val<(*tree)->val)
      insert(&(*tree)->left, item);
   else if(item->val>(*tree)->val)
      insert(&(*tree)->right, item);
}

void printout(node * tree) {
   if(tree->left) printout(tree->left);
   printf("%d\n",tree->val);
   if(tree->right) printout(tree->right);
}

void main() {
   node * curr, * root;
   int i;

   root = NULL;

   for(i=1;i<=10;i++) {
      curr = (node *)malloc(sizeof(node));
      curr->left = curr->right = NULL;
      curr->val = rand();
      insert(&root, curr);
   }

   printout(root);
}

Why is pointer-to-pointer used?

Answer 1

Because the insert method needs to modify the root of the tree.

Answer 2

a more precise answer will be : because the function need to replace content of given field (pointer)

Answer 3

can someone put here how to do the same logic without using that pointer-to-pointer

Answer 4

White board it. Or modify the sample code to do this:

for(i=1;i<=10;i++) {
  curr = (node *)malloc(sizeof(node));
  curr->left = curr->right = NULL;
  curr->val = rand();
  printf("before: %d\n", root);
  insert(&root, curr);
  printf("after: %d\n", root);
}

// printout(root);

The printed result looks like this:
before: 0
after: 3871888
before: 3871888
after: 3871888
before: 3871888
after: 3871888

Why is this?

Because it changes the pointer you pass to it.

How insert works: Insert traverses the tree. First it visits the current node. Then the left node (via recursion). Then the right node (via recursion). If it comes to a node that is empty (NULL), it replaces that node with item.

To do this, it dereferences the outer pointer, and assigns the value of the pointer "item" to that inner pointer.

In a general case, a pointer is just like an int, or a char. You pass a pointer by value. If you dereference it, you can modify whatever it points to, but not the pointer itself. If you pass a pointer-to-pointer, the inner pointer can be changed, but the outer pointer can't.

Here's some more pointer sample code to chew on:

#include <cstdio>
#include <cstdlib>

void some_func(int* value)
{
  *value = 12;
}

int main(int argc, char* argv[])
{
  int a = 5;
  printf("%d\n", a); // prints 5
  some_func(&a);
  printf("%d\n", a); // prints 12

  int b = 7;
  int* c = &b;
  printf("%d\n", b); // prints 7
  printf("%d\n", c); // prints 2029440 (some random memory address)
  some_func(c);
  printf("%d\n", b); // prints 12
  printf("%d\n", c); // prints 2029440 (the same value as before)
}

And:

#include <cstdio>
#include <cstdlib>

void some_other_func(int** other_value)
{
  *other_value = NULL;
}

int main(int argc, char* argv[])
{
  int b = 7;
  int* c = &b;

  printf("%d\n", c); // prints 4718288 (some random memory address)
  some_other_func(&c);
  printf("%d\n", c); // prints 0
}

Last but not least:

#include <cstdio>
#include <cstdlib>

void some_third_func(int* third_value)
{
  *third_value = 12;
  int** lets_modify_third_value = &third_value;
  *lets_modify_third_value = NULL;
}

int main(int argc, char* argv[])
{
  int b = 7;
  int* c = &b;

  printf("%d\n", b); // prints 7
  printf("%d\n", c); // prints 1637380 (some random memory address)
  some_third_func(c);
  printf("%d\n", b); // prints 12
  printf("%d\n", c); // prints 1637380 (same as before.  Note that the pointer was passed by value, so "third_value" was just a COPY of the address)
}

Answer 5

The alternative to an 'in out' parameter - a return value, would require an extra assignment in each level visited:

typedef node* node_ref;

node_ref insert ( node_ref tree, node_ref item) {  
    if ( !tree )  
        return item;

    if ( item -> val < tree -> val ) 
        tree -> left = insert ( tree -> left, item );
    else  if ( item -> val > tree -> val )
        tree -> right = insert ( tree -> right, item );

    return tree;
}

...
// in the loop 
   root = insert ( root, curr );

Another disadvantage with that approach ( or with the original code ) is that there is no way of telling whether the node was inserted; if you add a return value to indicate it, you don't have to leak curr if it is not inserted:

typedef node* node_ref;

bool insert ( node_ref *tree, node_ref item) {  
    if ( !*tree )  {
        *tree = item;
        return true;
    }

    if ( item -> val < ( *tree ) -> val ) 
        return insert ( & ( *tree ) -> left, item );

    if ( item -> val > ( *tree ) -> val )
        return insert ( & ( *tree ) -> right, item);

    return false;
}

...
// in the loop 
for ( int i = 1; i <= 10; ++i ) {
    node_ref curr = malloc ( sizeof ( node ) );

    curr -> left = curr -> right = NULL;
    curr -> val  = rand();

    if ( ! insert ( &root, curr ) )
        free ( curr );
}