Boh, io un'idea da valutare ce l'avrei, e se non sbaglio e' O(n), nel senso che si effettuano al massimo tanti passi quanti sono i nodi dell-albero.
Direi quindi che dovrebbe essere equivalente all'ottimo.
Una funzione ricorsiva alla quale si passa il nodo da valutare, e 2 valori, ovvero il range di validita' di quel nodo, chiamiamoli min e max.
Se il valore del nodo (value) non e' compreso nell'intervallo, allora male, ritornosubito false.
A qusto punto si valuta ricorsivamente sul sottoalbero di sinistra e su quello di destra.
Il range di validita' del sottoalbero di sinistra e' min - value
il rande di validita' del sottoalbero di destra e' value - max
Codice:
private bool Verify(Node center, int min, int max)
{
if ((center.Value < min) || (center.Value > max)) return false;
if ((center.left!=null) && (Verify(center.left, min, center.Value) == false)) return false;
if ((center.right!=null) && (Verify(center.right, center.Value, max) == false)) return false;
return true;
}
La prima chiamata sara'
return Verify (Radice,0,infinito);