Double pointer to binary search-tree node

Question

This might seem like a silly question to some of you and I know that I get things mixed up quite often but I need to understand the code so I can stop obsessing about it and focus on the real matter of why I need to use it.

So, in the code I see several assignments like this:

struct bst_node** node = root;
node = &(*node)->left;
node = &(*node)->right;

is there an invisible parenthesis here?

node = &((*node)->right);

This example is taken from literateprograms.org.

So to me it seems &(*node) is unnecessary and I might as well just write node->left instead, but the code seems to work where I can't make sense of it and I'm wondering if it's because I'm misunderstanding what's happening at those lines. Particularly, at one place in the code where it is deleting a node by constantly moving the "deleted" data to the bottom of the tree to safely remove the node without having to "break things", I'm lost because I don't get how

old_node = *node;
if ((*node)->left == NULL) {
    *node = (*node)->right;
    free_node(old_node);
else if ((*node)->right == NULL) {
    *node = (*node)->left;
    free_node(old_node);
} else {
    struct bst_node **pred = &(*node)->left;
    while ((*pred)->right != NULL) {
        pred = &(*pred)->right;
    }
    psudo-code: swap values of *pred and *node when the 
    bottom-right of the left tree of old_node has been found.
    recursive call with pred;
}

can keep the tree structure intact. I don't understand how this makes sure the structure is intact and would appreciate some help from somebody who knows what's going on. I interpret node being a local variable on the stack, created at the function call. Since it is a double pointer it points to a location in the stack (I assume this, since they did &(*node) previously to the function call), of either it's own stack or the function before, which then points to said node on the heap.

In the example code above what I think it is supposed to do is switch either left or right, since one of them is NULL, and then switch the one that isn't (assuming the other one isn't NULL?) As I said, I'm not sure about how this would work. My question mostly relates to the fact that I think &(*node) <=> node but I want to know if that's not the case etc.

Answer 1

node = &(*node)->right;

is there an invisible parenthesis here?

node = &((*node)->right);

Yes. It is taking the address of the right member of *node. The -> takes precedence over &; see C++ Operator Precedence (-> is 2 and & is 3 in that list) (it's the same general precedence as C).

So to me it seems &(*node) is unnecessary and I might as well just write node->left instead,

Your premise is off. There is no expression &(*node), as explained above, the & applies to the entire (*node)->left, not (*node).

In that code the double pointers are just that, a pointer to a pointer. Just as this works:

   int x = 0;
   int *xptr = &x;
   *xptr = 5;
   assert(x == 5);

This is the same, it changes the value of the pointer x:

   int someint;
   int *x = &someint;
   int **xptr = &x; 
   *xptr = NULL;
   assert(x == NULL);

In that code snippet you posted, assigning a pointer to *node changes the value of the pointer that node points to. So, e.g. (pseudo-ish code):

   typedef struct bst_node_ {
     struct bst_node_ *left;
     struct bst_node_ *right;
   } bst_node;

   bst_node * construct_node () {
     return a pointer to a new bst_node;
   }

   void create_node (bst_node ** destination_ptr) {
     *destination_ptr = construct_node();
   }

   void somewhere () {
     bst_node *n = construct_node();
     create_node(&n->left);  // after this, n->left points to a new node
     create_node(&n->right); // after this, n->right points to a new node
   }

Noting again that &n->left is the same as &(n->left) because of precedence rules. I hope that helps.

In C++ you can pass arguments to a function by reference, which is essentially the same as passing a pointer except syntactically it leads to code that is a bit easier to read.

Answer 2

That is useful

&(*node)->left <=>&((*node)->left)

The variable edited by this code is *node. I need the context fo this code to give more info