void
delete_by_merging (tree_type *node)
{tree_type tmp = *node;

 if (*node) {
   if (!(*node)->right)      /* the node has no right child: its left    */
     *node = (*node)->left;  /* child (if any) is attached to its parent */
   else if (!(*node)->left)  /* the node has no left child: its right    */
     *node = (*node)->right; /* child is attached to its parent;         */
   else {                    /* be ready for merging subtrees;           */
     tmp = (*node)->left;    /* 1. move left                             */
     while (tmp->right)      /* 2. and then right as far as possible;    */
       tmp = tmp->right;
     tmp->right =            /* 3. establish the link between the        */ 
       (*node)->right;       /*    the rightmost node of the left
                                   subtree and the right subtree;        */
     tmp = *node;            /* 4. */
     *node = (*node)->left;  /* 5. */
     }
   free(tmp);                /* 6. */
   }
}

void
delete (tree_type *root_addr, eltype key)
{tree_type node = *root_addr, previous = NULL;

 while (node) {
   if (node->key == key)
   break;
   previous = node;
   if (node->key > key)
     node = node->left;
   else node = node->right;
   }
 if (node->key == key)
   if (node == *root_addr)
     delete_by_merging (root_addr);
   else if (previous->left == node)
     delete_by_merging (&previous->left);
   else delete_by_merging (&previous->right);
 else if (*root_addr)
   printf("key %d is not in the tree\n", key);
 else printf("the tree is empty\n");
}

void
delete_by_copying (tree_type *node)
{tree_type previous, tmp = *node;

 if (!(*node)->right)               /* there is no right child for */ 
   *node = (*node)->left;           /* node;                       */
 else if (!(*node)->left)           /* no left child for node;     */
   *node = (*node)->right;
 else {
   tmp = (*node)->left;             /* node has both children;     */
   previous = *node;                /* 1. */
   while (tmp->right) {             /* 2. */
     previous = tmp;
     tmp = tmp->right;
     }
   (*node)->key = tmp->key;         /* 3. */
   if (previous == *node)
     previous->left  = tmp->left;
   else previous->right = tmp->left;/* 4. */
   }
 free(tmp);                         /* 5. */
}