Originariamente inviato da Shores
In un albero binario completo, ovvero in cui non manca mai nessun figlio fino alle foglie, i nodi di livello N sono semplicemente 2 elevato alla N.

Questo però non vuol dire che un algoritmo che li raggiunga sia di complessità di 2 elevato alla N, poichè esso è comunque costretto a visitare tutto l'albero sovrastante.

Quindi, nel caso peggiore, la complessità è pari alla somma per K che va da N a zero di 2 elevato K, ovvero pari a (2 elevato alla N+1) - 1.
Quindi sarebbe meglio, in questo caso, scegliere l'implementazione tramite array che accederebbe immediatamente alla posizione più a sinistra del livello e visiterebbe solo i nodi di quel livello?

Tralaltro l'algoritmo proposto da anx721 è inutilmente pesante, poichè procede nell'analisi di TUTTO l'albero anche quando il livello richiesto è stato superato; sarebbe stato più giusto attivare la ricorsione SOLO se il livello attuale era MINORE di quello cercato.

Infatti, i figli di un nodo di livello J non potranno che avere livello J+1; ciò implica che se ho trovato un nodo del livello cercato i suoi figli (e i suoi nipoti e così via) saranno di certo ignorabili poichè aventi livelli di certo superiori.
Non vorrei abusare... ma tu come lo modificheresti? E la complessità come diventerebbe?

In ogni caso grazie!