Il problema è in search(): a sinistra ci devi andare se la chiave del nodo corrente risulta maggiore di k, non minore

codice:
int search(Tree t, int k)
{
    struct Nodo *n = t;
    int depth = 0;

    while (n != NULL) {
        depth++;
        if (n->key > k)
            n = n->left;
        else    if (n->key == k)
                    return depth;
                else
                    n = n->right;
    }

    return 0;
}
la prossima volta comunque riporta il codice con i tag code come previsto anche dal regolamento, altrimenti il codice diventa illeggibile.