Binary Tree constructor sometimes works, sometimes not

[tigrerojo]

For a college workshop I had to implement a Set template class following a Binary Tree structure, and have it succesfully run a series of preset Tests; two of the tests first initialize a set using an IDENTICAL set of steps and then tries to get specific values off them. The thing is, the first test initializes the tree perfectly and finishes succesfully, while the second test fails after trying to insert the third element.
I'm not used to analysing the debugger's info, but ALL my attempts end with a 'Segmentation Fault', and a Tree whose _head node has a wrong value (4 instead of 5)and whose left child points to the head itself, which obviously doesn't happen in the first, identical test.

The tests in question:

  TEST(conjunto_test, test_insertar_cinco_valores) {
    Conjunto<int> c;
    c.insertar(5);
    c.insertar(4);
    c.insertar(7);
    c.insertar(6);
    c.insertar(8);
    EXPECT_EQ(c.cardinal(), 5);
  }



TEST(conjunto_test, test_minimo) {
    Conjunto<int> c;
    c.insertar(5);
    c.insertar(4);
    c.insertar(7);
    c.insertar(6);
    c.insertar(8);
    EXPECT_EQ(c.minimo(), 4);
}

I made several different versions of the following functions (specially of the ones that receive pointers as parameters) and they all gave me the same result, so I'll only post the last ones I tried; some of the function and variable names are in spanish, so let me know if I should translate them for this post:

template <class T> //insert function
void Conjunto<T>::insertar(const T& clave) {
	Nodo* aux_padre = _raiz;
	if (aux_padre == NULL){
	    _raiz = new Nodo(clave);
	    _cont++;
	}else{
	    Nodo* hijo_si_esta = buscar(aux_padre,clave);
        if (hijo_si_esta == NULL){
		    Nodo* hoja = new Nodo(clave);
		    if (clave > aux_padre->valor){
                aux_padre->der = hoja;
		    }else{
             aux_padre->izq = hoja;
		    }
		    _cont++;
	    }
    }
}



template <class T>
void Conjunto<T>::remover(const T& clave) { 
    Nodo* aux_p = _raiz;
    Nodo* aux_h = buscar(aux_p, clave);
    
    if (aux_h != NULL){
    	if (aux_h->izq == NULL){
    		if (aux_p->izq == aux_h){
    			aux_p -> izq = aux_h -> der;
    			delete aux_h;
    		}else{
    			aux_p -> der = aux_h -> der;
    			delete aux_h;
    		}
    	}else if (aux_h->der == NULL){ //there is only a left child
    		if (aux_p->izq == aux_h){ 
    			aux_p -> izq = aux_h -> izq;
    			delete aux_h;
    		}else{
    			aux_p -> der = aux_h -> izq; 
    			delete aux_h;
    		}
    	}else{ // entro solo si a_buscar tiene ambos hijos
    		Nodo* aux_hsucp = aux_h;
    		Nodo* aux_hsuc = hijo_sucesor(aux_hsucp);  
    		aux_h ->  valor = aux_hsuc->valor; 

    		//3 cases
    		if (aux_hsucp == aux_h){ //suc is the immediate right child
    			aux_hsuc->izq = aux_h->izq;
    			if (aux_p->izq == aux_h){
    				aux_p->izq = aux_hsuc;
    			}else{
    				aux_p->der = aux_hsuc;
    			}
    			delete aux_h;
    		}else if (aux_hsuc->der == NULL){ //suc is a leaf
    			aux_h->valor = aux_hsuc->valor;
    			aux_hsucp->izq = NULL;
    			delete aux_hsuc;
    		}else{//suc has a right child
    			aux_h->valor = aux_hsuc->valor;
    			aux_hsucp->der = aux_hsuc->der;
    			delete aux_hsuc; 
    		}
    	}
    	_cont--;
    } 
}


struct Nodo
        {
            Nodo(const T& v):valor(v),izq(NULL),der(NULL){};
            T valor;
            Nodo* izq;
            Nodo* der; 
        };


Nodo* buscar(Nodo *&raiz, const T& elem){
            Nodo* aux = raiz;
        	if (aux == NULL){
        		return aux;
        	}
        	if (aux->valor == elem){
        		return aux; //unir los dos?
            }else if (aux->valor > elem){
        	    if (aux->izq != NULL){
                    raiz = raiz->izq;
                    return buscar(raiz,elem);
        	    }else return NULL;
            }else{
        	    if (aux->der != NULL){
        	        if (aux->der != NULL){
                        raiz = raiz->der;
                        return buscar(raiz,elem);
        	        }else return NULL;
        	    }
        	}
}


Nodo* hijo_sucesor(Nodo *&padre){
        Nodo* aux = padre->der;
        while (aux->izq != NULL){
            padre = aux;
        	aux = aux->izq;
            }
        return aux;
}


void borrar_cascada(Nodo *&padre){
        	Nodo* aux = padre;
        	if (aux != NULL){
        	    borrar_cascada(aux->der);
                borrar_cascada(aux->der);
                delete aux ;
        	}
}

Does anyone have a clue as to what the problem might be? I tried changing my search (buscar()) delete (borrar_cascada()) and succesor searcher (hijo_sucesor()) to receive both &*Nodo, **Nodo and *Nodo as a parameter based on some info I found online, but it all ends up with the same error...

[ne555]

- indent your code properly (don't mix tabs and spaces)
- don't abbreviate your names and remove the `aux' prefix.
then `aux_hsuc' may become `sucesor' and
`aux_hsucp' will be `padre_del_sucesor'
which makes easier to distinguish and gives them a meaning.


your tests use the `.insertar()' function, ¿why do we care about .remover()?
¿are you using .remover() in your code?
if you want to test `a', then do `a', don't do `xyz_a_zyx' when have no idea if the other functions work.

that said, .remover() is incorrect
you say hijo = buscar(padre, clave);
however, in buscar() the only time when you don't return NULL is this

Nodo* buscar(Nodo *&raiz, const T& elem){
	aux = raiz;
	if (aux->valor == elem)
		return aux;

when you don't return NULL, you return `raiz', so both `hijo' and `padre' are the same node.

I stopped there as the names were making me dizzy. You'll have to provide a minimal run-able example so we can use a debugger.



> I tried changing my search, delete and succesor searcher to receive both
> &*Nodo, **Nodo and *Nodo as a parameter
don't voodoo code, think on what you are doing and why


almost forgot

borrar_cascada(aux->der);
borrar_cascada(aux->der);

note that you kill the right son twice.