[Java] Verifica se l'albero binario è triangolare

[absinth]

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 è :
[img]http://i.imgur.com/b4N0z1I.png?1[/img]

La mia soluzione:

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();
}

[apatriarca]

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.

[absinth]

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?

[apatriarca]

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.

[absinth]

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