Algorithms and Data Structures · Middle · Question 52 of 75
What is the space complexity of a recursive DFS on a tree of height h?
- 1O(n²) for the visited set
- ✓Correct answer: O(h) for the call stack
- 3O(1), because nothing is stored
Explanation
At any time the stack holds one frame per level of the current path. For a balanced tree h is log n; for a degenerate one it's n.