Árvore Binária de Pesquisa, duvida sobre elementos

Olá!

Segue o seguinte código:

#include <iostream>
#include <cstdlib>

#define TIPO int

using namespace std;
struct nodo {

 nodo *esquerda;
 TIPO informacao;
 nodo *direita;
 nodo (TIPO info) :
 informacao (info),
 esquerda (0),
 direita (0) {}
};

nodo *P;

struct nodo insere (nodo tree, TIPO informacao) {

 if (tree == NULL)
 tree = new nodo (informacao);
 else if (informacao < tree-> informacao)
 tree-> esquerda = insere(tree-> esquerda, informacao);
 else if (informacao > tree-> informacao)
 tree-> direita = insere(tree-> direita, informacao);
 return tree;
}

void infixa (nodo *tree) {

 if (tree != NULL) {
 infixa(tree-> esquerda);
 cout << " " << tree-> informacao;
 infixa(tree-> direita);
 }
}

void prefixa (nodo *tree) {

 if (tree != NULL) {
 cout << " " << tree-> informacao;
 prefixa(tree-> esquerda);
 prefixa(tree-> direita);
 }
}

void posfixa (nodo *tree) {

 if (tree != NULL) {
 posfixa(tree-> esquerda);
 posfixa(tree-> direita);
 cout << " " << tree-> informacao;
 }
}

int main() {

 nodo *raiz = 0;
 TIPO valor;
 int elementos, qtd;
 int cont = 0;
 cin >> qtd;
 while((qtd --) && (cin >> elementos)) {
 while (elementos --) {
 cin >> valor;
 raiz = insere (raiz, valor);
 }
 cont++;
 cout << "Case " << cont << ":" << endl;
 cout << "Pre.:";
 prefixa (raiz);
 cout << endl;

 cout << "In.:";
 infixa (raiz);
 cout << endl;

 cout << "Post:";
 posfixa (raiz);
 cout << endl;
 cout << endl;
 }

 return 0;
}

	Estou a aprender sobre essa estrutura de dados, precisaria de uma forma de "limpar" ou remover todos os elementos da árvore, após cada caso de teste, mas não tenho ideia concreta de como implementar isso. Pensei em remover cada elemento, mas não sei se seria a melhor forma de fazer. Alguém poderia dar um auxílio?

	Grato pela atenção!