Problema livello BST C++

Salve, ho un problema con un esercizio che mi chiede di creare un albero di ricerca binaria, inserire od eliminare i valori e successivamente trovare il livello di valori chiave; tutti questi dati vengono presi da un file di input di 100 righe cioè da ripetere 100 volte con input diversi, vi lascio un esempio:
int 2 1 ins:10 ins:20 20
double 2 1 ins:1.9 ins 2.9 2.9
l'ultimo numero è il valore chiave di cui devo trovare il livello.
qui il codice:

#include <iostream>
#include <fstream>
#include <sstream>

#include <string>
#define INPUT_FILE "input.txt"
#define OUTPUT_FILE "output.txt"

using namespace std;

fstream infile, outfile;

template <typename H>
struct Nodo
{
	H val;
	Nodo<H>* padre, *sinistro, *destro;
};

template <typename H>
class BST
{
	private:
		Nodo<H>* radice;
	public:
		BST() : radice(NULL) {}
		void ins(H val)
		{
			Nodo<H>* nuovo = new Nodo<H>();
			nuovo->sinistro=nuovo->destro=NULL;
			nuovo->val=val;
			Nodo<H>* x = radice;
			Nodo<H>* y = NULL;
			while (x!=NULL)
			{
				y=x;
				if (x->val>val)
					x = x->sinistro;
				else 
					x = x->destro;
			}
			nuovo->padre = y;
			if (y==NULL)
				radice = nuovo;
			else if (y->val>val)
				y->sinistro = nuovo;
			else 
				y->destro = nuovo;
		}
		Nodo<H>* minimo(Nodo<H>* m)
		{
			if (m)
			{
				Nodo<H>* x = m;
				while (x->sinistro)
					x = x->sinistro;
			}
			return m;
		}
		Nodo<H>* ricerca(H val)
		{
			Nodo<H>* x = radice;
			while ((x!=NULL)&&(x->val!=val))
			{
				if (x->val>val)
					x = x->sinistro;
				else
					x = x->destro;
			}
			return x;
		}
		void trapianta(Nodo<H>* u, Nodo<H>* v)
		{
			if (u->padre==NULL)
				radice = v;
			else if(u->padre->sinistro==u)
				u->padre->sinistro=v;
			else
				u->padre->destro=v;
			if (v)
				v->padre = u->padre;
		}
		void cancella(H val)
		{
			Nodo<H>* z = ricerca(val);
			if(z->sinistro==NULL)
				trapianta(z, z->destro);
			else if(z->destro==NULL)
				trapianta(z, z->sinistro);
			else 
			{
				Nodo<H>* y = minimo(z->destro);
				if(y->padre!=z)
				{
					trapianta(y, y->destro);
					y->destro=z->destro;
					y->destro->padre=y;
				}
				trapianta(z, y);
				y->sinistro=z->sinistro;
				y->sinistro->padre=y;
			}
		}
		int livello(Nodo<H>* l)
		{
			int cont=0;
			Nodo<H>* aux = radice;
            if (l->val==aux->val)
                return 0;
			while (l->padre->val!=aux->val)
			{
				cont++;
				l = l->padre;
			}
			return cont+1;
		}
};

int main()
{
	infile.open(INPUT_FILE, fstream::in);
	outfile.open(OUTPUT_FILE, fstream::out);
	string type, query;
	int N, M;
	int chiave;
	double chiaved;
	for (int i=0; i<100; i++)
	{
		cout << "inizio ciclo..." << endl;
		infile >> type;
		infile >> N >> M;
		if(type=="int")
		{
			BST<int> *tree = new BST<int>();
			int k;
			for (int i=0; i<N; i++)
			{
				infile >> query;
				if(query[0]=='i')
				{
					stringstream buffer(query.substr(4));
					buffer >> k;
					tree->ins(k);
				}
				if(query[0]=='c')
				{
					stringstream buffer(query.substr(5));
					buffer >> k;
					tree->cancella(k); 
				}
			}
			for (int i=0; i<M; i++)
			{
				infile >> chiave;
				Nodo<int> *nodo = new Nodo<int>();
				nodo = tree->ricerca(chiave);
				int liv = 0;
				liv = tree->livello(nodo);
				outfile << liv << " ";			
			}
		}
		if(type=="double")
		{
			BST<double> *tree=new BST<double>();
			double k;
			for(int i=0; i<N; i++)
			{
				infile >> query;
				if(query[0]=='i')
				{
					stringstream buffer(query.substr(4));
					buffer >> k;
					tree->ins(k);
				}
				if(query[0]=='c')
				{
					stringstream buffer(query.substr(5));
					buffer >> k;
					tree->cancella(k);
				}
			}
			for(int i=0; i<M; i++)
			{
				infile >> chiaved;
                Nodo<double> *nodo = new Nodo<double>();
                nodo = tree->ricerca(chiaved);
                int liv = 0;
                liv = tree->livello(nodo);
                outfile << liv << " ";
			}
		}
		outfile << endl;
	}
	cout << "fine ciclo..." << endl;
	infile.close();
	outfile.close();
}

il problema è che esegue il codice 7-8 volte e va in segmentaion fault e non riesco a capire perché, spero possiate aiutarmi.