Nel tuo codice originale no, dato che ogni if viene controllato a prescindere dal precedente. Mettendo l'else, invece, il primo if verificato bypassa gli altri.
Tra l'altro c'è un errore subdolo in quella funzione: ossia che i vari annullamenti dei puntatori rimangono locali alla funzione, per cui quando si entra in uno dei rami ricorsivi e poi se ne esce, i puntatori ->dx o ->sx non sono NULL, ma non sono nemmeno più validi. Il che significa che oltre a fallire i controlli, si fa la free() di un puntatore sporco.
Per trasmettere le modifiche all'esterno è necessario passare un puntatore al puntatore.
La sintassi è quella che è, però modificando così non ho avuto più problemi:
codice:
void cancellazione_elemento(tree* Y, int elem)
{
    if ((*Y)->value < elem)
        cancellazione_elemento(&(*Y)->dx, elem);
    else if ((*Y)->value > elem)
        cancellazione_elemento(&(*Y)->sx, elem);
    else//se Y->value risulta uguale all elemento che vogliamo eliminare
    {
        if ((*Y)->sx == NULL && (*Y)->dx == NULL)
        {
            free((*Y));
            (*Y) = NULL;
        }
        else if ((*Y)->sx != NULL && (*Y)->dx == NULL)
        {
            (*Y)->value = (*Y)->sx->value;
            free((*Y)->sx);
            (*Y)->sx = NULL;
        }
        else if ((*Y)->sx == NULL && (*Y)->dx != NULL)
        {
            (*Y)->value = (*Y)->dx->value;
            free((*Y)->dx);
            (*Y)->dx = NULL;
        }
        else if ((*Y)->sx != NULL && (*Y)->dx != NULL)
            printf("Non posso eliminare questo nodo poichè entrambi i suoi rami contengono dei dati!\n");
    }
    stampa_tutto((*Y));
}