title: Double pointer to binary search-tree node
body: <p>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.</p>
  
  <p>So, in the code I see several assignments like this:</p>
  
  <pre><code>struct bst_node** node = root;
  node = &amp;(*node)-&gt;left;
  node = &amp;(*node)-&gt;right;
  
  is there an invisible parenthesis here?
  
  node = &amp;((*node)-&gt;right);
  </code></pre>
  
  <p>This example is taken from literateprograms.org.</p>
  
  <p>So to me it seems &amp;(*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</p>
  
  <pre><code>old_node = *node;
  if ((*node)-&gt;left == NULL) {
      *node = (*node)-&gt;right;
      free_node(old_node);
  else if ((*node)-&gt;right == NULL) {
      *node = (*node)-&gt;left;
      free_node(old_node);
  } else {
      struct bst_node **pred = &amp;(*node)-&gt;left;
      while ((*pred)-&gt;right != NULL) {
          pred = &amp;(*pred)-&gt;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;
  }
  </code></pre>
  
  <p>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 &amp;(*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.</p>
  
  <p>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 &amp;(*node) &lt;=> node but I want to know if that's not the case etc.</p>