Algorithmen und Datenstrukturen · Middle · Frage 52 von 75
Welche Platzkomplexität hat eine rekursive DFS auf einem Baum der Höhe h?
- 1O(n²) für die Menge der besuchten Knoten
- 2O(h) für den Call Stack
- 3O(1), weil nichts gespeichert wird
Antwort zeigen
Richtige Antwort: O(h) für den Call Stack
Erklärung
Zu jedem Zeitpunkt hält der Stack einen Frame pro Ebene des aktuellen Pfads. Bei einem balancierten Baum ist h log n, bei einem entarteten n.