ironicaldiction ironicaldiction - 3 months ago 6
C Question

Validate the claim that it is better to use pointers to pointers while working with binary trees

In this video (a section/recitation for an online course called CS50), around 1h00m00s, the student instructor goes into pointers-to-pointers and why it is more efficient useful to implement insert on the binary tree this way. At least, that is what I'm getting from the argument.

I did a recursive implementation both ways. I don't see why Option A is better than Option B in the below...perhaps you could help me reason this out or point me in the right direction if I'm misunderstood?

Option A (with pointers-to-pointers)



bool insert(int value, node* tree)
{
node** tmptree = &tree;
// make sure the tree itself isn't null
if(*tmptree != NULL)
{
if(value == (*tmptree)->value)
{
return false;
}
else if(value < (*tmptree)->value)
{
tmptree = &(*tmptree)->left;
// we must be at a null leaf!
if(*tmptree == NULL)
{
// make sure we built a leaf
*tmptree = build_node(value);
if(*tmptree == NULL)
{
return false;
}
return true;
}
else
{
return insert(value, *tmptree);
}
}
else
{
tmptree = &(*tmptree)->right;
if(*tmptree == NULL)
{
*tmptree = build_node(value);
if(*tmptree == NULL)
{
return false;
}
return true;
}
else
{
return insert(value, *tmptree);
}
}
}
return false; // if the tree is null
}


Option B (regular ptrs)



bool insert(int value, node* tree)
{
if(tree != NULL)
{
if(value == tree->value)
{
return false;
}
else if(value < tree->value)
{
if(tree->left == NULL)
{
node* tmp = build_node(value);
if(tmp != NULL)
{
tree->left = tmp;
return true;
}
return false;
}
else
{
return insert(value, tree->left);
}
}
else
{
if(tree->right == NULL)
{
node* tmp = build_node(value);
if(tmp != NULL)
{
tree->right = tmp;
return true;
}
return false;
}
else
{
return insert(value, tree->right);
}
}
}
return false; // if the tree is null
}


The build_node function:

node* build_node(int value)
{
node* node = malloc(sizeof( node ));
if(node == NULL)
return NULL;
node->value = value;
node->left = NULL;
node->right = NULL;
return node;
}

Answer

I believe you have misunderstood why there is a pointer-to-pointer in the original code. The "Option a" doesn't make any sense, there is no advantage of using pointer-to-pointer just for the sake of it.

The only reason you would use pointer-to-pointer is because you want to change the pointed-to address and return it to the caller.

For example

void func (int** ptr)
{
  *ptr = something;
}

func(&my_ptr);

// is the very thing same as

int* func (int* ptr)
{
  return something;
}

my_ptr = func(my_ptr);

You can't use the second version and type ptr = something inside the function, because ptr is a local variable and will cease to exist once you leave the function. Assigning something to it won't affect the original pointer at the caller's side.

The only advantage of the pointer-to-pointer version is that the returned type can be used for something else, like for example returning an error code.

And that seems to be exactly why the guy in that video used it. His function looks like

bool insert (int value, node** tree);

where the *tree is assigned to point at another address from inside the function and the bool is used as a status code, when he reaches the end of a tree branch.