Algoritmos y Estructuras de Datos (VJ1215)

bool Conjunto::noHayHijoSinHermano() const {
   return raiz == nullptr || noHayHijoSinHermano(raiz);
}

bool Conjunto::noHayHijoSinHermano(Nodo * n) const {
   if (n->izquierdo == nullptr && n->derecho == nullptr)
      return true;
   if (n->izquierdo != nullptr && n->derecho != nullptr)
      return noHayHijoSinHermano(n->izquierdo) && noHayHijoSinHermano(n->derecho);
   return false;
}
      

Otra forma de expresar lo mismo es:

bool Conjunto::noHayHijoSinHermano() const {
   return raiz == nullptr || noHayHijoSinHermano(raiz);
}

bool Conjunto::noHayHijoSinHermano(Nodo * n) const {
   return (n->izquierdo == nullptr && n->derecho == nullptr)
          || (n->izquierdo != nullptr
              && n->derecho != nullptr
              && noHayHijoSinHermano(n->izquierdo)
              && noHayHijoSinHermano(n->derecho));
}
      

El coste temporal de ambas versiones es O(n) siendo n la cantidad de nodos del árbol.