#include <algorithm>
#include <iostream>

struct nodo {
   int valor;
   nodo* izq;
   nodo* der;
};

void inserta(nodo*& p, int v) {
   if (p == nullptr) {
      p = new nodo{v, nullptr, nullptr};
   } else if (v < p->valor) {
      inserta(p->izq, v);
   } else {
      inserta(p->der, v);
   }
}

bool busca(nodo* p, int v) {
   if (p == nullptr) {
      return false;
   } else if (v == p->valor) {
      return true;
   } else if (v < p->valor) {
      return busca(p->izq, v);
   } else {
      return busca(p->der, v);
   }
}

int altura(nodo* p) {
   if (p == nullptr) {
      return 0;
   } else {
      int h1 = altura(p->izq);
      int h2 = altura(p->der);
      return std::max(h1, h2) + 1;
   }
}

int peso(nodo* p) {     // peso = cantidad de nodos
   if (p == nullptr) {
      return 0;
   } else {
      int t1 = peso(p->izq);
      int t2 = peso(p->der);
      return t1 + t2 + 1;
   }
}

nodo* minimo(nodo* p) {
   if (p == nullptr) {
      return nullptr;
   } else if (p->izq != nullptr) {
      return minimo(p->izq);
   } else {
      return p;
   }
}

nodo* maximo(nodo* p) {
   if (p == nullptr) {
      return nullptr;
   } else if (p->der != nullptr) {
      return maximo(p->der);
   } else {
      return p;
   }
}

void preorden(nodo* p) {
   if (p != nullptr) {
      std::cout << p->valor << " ";
      preorden(p->izq);
      preorden(p->der);
   }
}

void posorden(nodo* p) {
   if (p != nullptr) {
      posorden(p->izq);
      posorden(p->der);
      std::cout << p->valor << " ";
   }
}

void en_orden(nodo* p) {
   if (p != nullptr) {
      en_orden(p->izq);
      std::cout << p->valor << " ";
      en_orden(p->der);
   }
}

int main( ) {
   nodo* raiz = nullptr;
   inserta(raiz, 5);
   inserta(raiz, 7);
   inserta(raiz, 3);
   inserta(raiz, 6);
   inserta(raiz, 2);
   inserta(raiz, 1);
   inserta(raiz, 9);

   for (int i = 0; i <= 10; ++i) {
      std::cout << i << ": " << busca(raiz, i) << "\n";
   }
   std::cout << "\n";

   std::cout << "altura: " << altura(raiz) << "\n";
   std::cout << "peso: "   <<   peso(raiz) << "\n";
   std::cout << "minimo: " << minimo(raiz)->valor << "\n";
   std::cout << "maximo: " << maximo(raiz)->valor << "\n";

   std::cout << "preorden: ";
   preorden(raiz);
   std::cout << "\n";
   std::cout << "posorden: ";
   posorden(raiz);
   std::cout << "\n";
   std::cout << "en_orden: ";
   en_orden(raiz);
   std::cout << "\n";
}