BSTInsertDelayedPointer.c

struct node* BSTTreeInsert(struct node* p, struct node* r) { 
  struct node* y = NULL; 

  struct node* x = r; 

  while (x != NULL) { 
    // y is one step behind y = x; 
    if (x -> key < p -> key) { 
        x = x -> rgt; 
    } else { 
        x = x -> lft; 
    }
  }

  // Three cases
  if (y == NULL) r = p; 
  else if (y->key < p->key) y->rgt = p; 
  else y->lft = p; 
  return r; 
}