#include <iostream>
#include <queue>
#include <stack>

using namespace std;

#include "Conjunto.h"

Conjunto::Nodo::Nodo(int elDato) : dato{elDato}, izquierdo{nullptr}, derecho{nullptr} {
}

Conjunto::Conjunto() : raiz{nullptr} {
}
  
void Conjunto::insertar(int unDato) {
   insertar(unDato, raiz);
}

void Conjunto::insertar(int unDato, Nodo * & n) {
   if (n == nullptr)
      n = new Nodo(unDato);
   else if (unDato < n->dato)
      insertar(unDato, n->izquierdo);
   else if (unDato > n->dato)
      insertar(unDato, n->derecho);
   // No insertamos duplicados
}

int Conjunto::minimoEnSubarbol(Nodo * n) const { // Sabiendo que n != nullptr
   if (n->izquierdo == nullptr)
      return n->dato;
   return minimoEnSubarbol(n->izquierdo);
}

void Conjunto::eliminar(int unDato) {
   eliminar(unDato, raiz);
}

void Conjunto::eliminar(int unDato, Nodo * & n) {
   if (n == nullptr)
      return;
   if (unDato < n->dato)
      eliminar(unDato, n->izquierdo);
   else if (unDato > n->dato)
      eliminar(unDato, n->derecho);
   else if (n->izquierdo != nullptr && n->derecho != nullptr) {
      n->dato = minimoEnSubarbol(n->derecho);
      eliminar(n->dato, n->derecho);
   } else {
      Nodo * basura = n;
      if (n->izquierdo != nullptr)
	 n = n->izquierdo;
      else
	 n = n->derecho;
      delete basura;
   }
}

bool Conjunto::buscar(int unDato) const {
   Nodo * n = raiz;
   while (n != nullptr) {
      if (unDato < n->dato)
	 n = n->izquierdo;
      else if (unDato > n->dato)
	 n = n->derecho;
      else
	 return true;
   }
   return false;
}

/*
bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;

   queue<Nodo *> cola;
   
   cola.push(raiz);
   int tallaNivel = 1;
   int profundidad = 0;

   while (tallaNivel > 0) {

      for (int i = 0; i < tallaNivel; i++) {
	 Nodo * nodo = cola.front();
	 cola.pop();
	 if (nodo->izquierdo != nullptr) {
	    if (profundidad + 1 == p)
	       return true;
	    cola.push(nodo->izquierdo);
	 }
	 if (nodo->derecho != nullptr) {
	    if (profundidad + 1 == p)
	       return true;
	    cola.push(nodo->derecho);
	 }
      }

      tallaNivel = cola.size();
      profundidad++;

   }

   return false;

}
*/

/*
bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;
   
   queue<Nodo *> cola;
   
   cola.push(raiz);
   int tallaNivel = 1;
   int profundidad = 0;

   while (! cola.empty()) {
      
      Nodo * nodo = cola.front();
      cola.pop();

      if (nodo->izquierdo != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(nodo->izquierdo);
      }

      if (nodo->derecho != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(nodo->derecho);
      }

      if (--tallaNivel == 0) {
	 profundidad++;
	 tallaNivel = cola.size();
      }

   }
   
   return false;

}
*/

/*
bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;

   struct Par {
      Nodo * nodo;
      int profundidad;
      Par(Nodo * n, int p) : nodo{n}, profundidad{p} {}
   };

   queue<Par> cola;
   
   cola.push(Par(raiz, 0));

   while (! cola.empty()) {

      Nodo * nodo = cola.front().nodo;
      int profundidad = cola.front().profundidad;
      cola.pop();

      if (nodo->izquierdo != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(Par(nodo->izquierdo, profundidad + 1));
      }

      if (nodo->derecho != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(Par(nodo->derecho, profundidad + 1));
      }

   }

   return false;

}
*/

/*
bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;

   struct Par {
      Nodo * nodo;
      int profundidad;
      Par(Nodo * n, int p) : nodo{n}, profundidad{p} {}
   };

   stack<Par> pila;
   
   pila.push(Par(raiz, 0));

   while (! pila.empty()) {

      Nodo * nodo = pila.top().nodo;
      int profundidad = pila.top().profundidad;
      pila.pop();

      if (nodo->izquierdo != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 pila.push(Par(nodo->izquierdo, profundidad + 1));
      }

      if (nodo->derecho != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 pila.push(Par(nodo->derecho, profundidad + 1));
      }

   }

   return false;

}
*/

bool Conjunto::verificarProfundidad(int p) const {

   return verificarProfundidad(p, raiz);

}

bool Conjunto::verificarProfundidad(int p, Nodo * n) const {

   if (n == nullptr)
      return false;

   if (p == 0)
      return true;

   return verificarProfundidad(p - 1, n->izquierdo) || verificarProfundidad(p - 1, n->derecho);

}