Why we use “&(*” statement when double pointer to

Question

void instert(NODE**root, int value)
{
    ...
    insert(&(*root)->left,value);
    ...
}

void search(NODE*root, int value)
{
    ...
    search(root->left, value);
    ...
}

Why we use "&" here: insert(&(*root)->left,value); But we do not use "&" here: search(root->left, value);

Answer 1

&(* isn't a statement.

It is parts of the &-operator being applied to the expression (*root)->left.

Answer 2

An extra level of indirection is added to insert function so that it could modify the pointer. This is not necessary in case of the search function, because it never modifies the pointer passed to it.

Specifically, there needs to be a place in the insert function that does something like this:

*root = malloc(sizeof(NODE));
(*root)->left = NULL;
(*root)->right = NULL;
(*root)->value = value;

This would modify the pointer which is pointed to by the pointer to pointer.

Note that it is possible to avoid this extra level of indirection by returning the new value of the pointer from insert, like this:

NODE* insert(NODE*root, int value) {
    ...
    root->left = insert(root->left, value);
    ...
}

However, this changes the way in which all callers must call insert, including the top-level caller: rather than writing

insert(&root, value);

he would be forced to write

root = insert(root, value);

Answer 3

The expression:

*root->left

Is equivalent to:

*(root->left)

Due to operator precedence.

So you need:

(*root)->left

If you want the left member that *root points to.

And then:

&(*root)->left

Is the pointer to the left member of *root, which is then of type NODE **, what the insert function requires.