BSTDelete.c

struct node* BSTreeDelete(struct node* root, struct node* x) {
  u = root; v = NULL; 
  while (u != x) { 
    v = u; 
    if (x->key < u->key) u = u->lft; 
    else u = u->rgt; 
  }

  if (u->rgt == NULL) { 
    if (v == NULL) root = u->lft; 
    else if (v->lft == u) v->lft = u->lft; 
    else v->rgt = u->lft; 
  else if (u->lft == NULL) { 
    if (v == NULL) root = u->rgt; 
    else if (v->lft == u) v->lft = u->rgt; 
    else v->rgt = u->rgt; 
  else { 
    p = x->lft; 
    q = p; 
    while (p->rgt != NULL) { q = p; p = p->rgt; } 
  
    if (v == NULL) root = p; 
    else if (v->lft == u) v->lft = p; 
    else v->rgt = p; 
    
    p->rgt = u->rgt;
    if (q != p) { 
      q->rgt = p->lft; 
      p->lft = u->lft; 
  } 
  return root 
}