Matematicamente.it

Ciao a tutti! Ho un dubbio riguardo a un algoritmo che ho appena scritto. Mi sembra troppo breve rispetto alle alternative della soluzione quindi forse ho sbagliato ma non trovo l'errore.
Forse i confronti con null non vanno bene?. E' da un sacco che non studio java
La mia idea è che se un albero binario è triangolare, allora lo sono anche i sui sotto-alberi. A quanto pare risulta O(n).

La consegna è :


La mia soluzione:

Codice:

static <T> boolean isTriangular(BinaryTree<T> a)
{
   return isTriangularPos(a.root());
}

static <T> boolean isTriangularPos(Position<T> v)
{
   if(v.hasLeft()&&v.hasRight())
   {
      if (v.left().isExternal()||v.right().isExternal())
         return v.left().isExternal()==v.right().isExternal();
      return isTriangularPos(v.left())&&isTriangularPos(v.right());
   }
   return v.hasLeft()==v.hasRight();
}


Non ho mai sentito parlare di albero triangolari. Intendi dire un albero completo (con \(2^N\) nodi e completamente bilanciato?\). Se è così allora la tua idea non funziona perché i due figli possono essere completi, ma avere un numero diverso di nodi. Quello che stai effettivamente testando è in pratica che ogni nodo è un foglia o un nodo interno con due figli. Devi insomma tenere anche traccia della profondità massima raggiunta nei due sottoalberi.

L'albero binario triangolare ha $2^{h+1}-1$ nodi dove $h$ è l'altezza e ha questa struttura:


A quanto pare l'hai capito bene ma non riesco a trovare l'errore cioè seguendo il tuo ragionamento un albero di questo tipo:

dovrebbe dare TRUE?

Allora è strano perché al primo ciclo uno dei due figli è una foglia mentre l'altro no quindi nell'IF interno
return v.left().isExternal()==v.right().isExternal() mi darà FALSE.

se no allora per favore puoi farmi vedere o spiegare un esempio di non triangolare che verifica le condizioni?

Si, devi andare un po' più profondo per vederlo per via del secondo test che fai. Considera un albero con il sottoalbero sinistro triangolare di profondità 4 e quello destro di profondità 2.

ah già devo per forza tener conto della profondità, grazie mille