- Codice:
algoritmo DFS( nodo r )
Pila S
S.push( r )
while( not S.isEmpty() ) do
u <- S.pop()
if( u != null ) then
visita u
S.push( figlio dx di u )
S.push( figlio sx di u )
Per quanto riguarda il costo temporale ho cercato di considerare il caso peggiore. L'albero che visitiamo ha, per ogni nodo, al più due figli. Supponiamo che l'albero T abbia esattamente $n$ allora il caso peggiore è quando $T$ degenera in lista, poiché in questo caso, per ogni nodo di $T$ si impilano due record ( eventualmente nulli ) su S. Da ciò otteniamo che la grandezza della pila è $2n$ nel caso peggiore e dunque le iterazioni del ciclo while sono $O( n )$ da cui $T_{w o r st} = O( n ) $
Per quanto riguarda lo spazio sempre con lo stesso caso peggiore si ha che $S( n ) = 2n$ da cui $S(n) = O(n)$
E' corretto?