Space complexity of recursive DFS on a binary tree of height h?
Options
- O(1), since no extra memory is allocated
- O(h) for the recursion call stack (Correct option)
- O(n²), since each node is visited twice
- O(log h) for the depth of the call stack
Answer
O(h) for the call stack
Why
Recursive DFS keeps one call-stack frame for each node on the current path from the root. The longest path has h nodes, so memory is O(h).
For a balanced tree h ≈ log n; for a completely skewed tree h = n.
BFS instead keeps a whole level in its queue: O(width).
Remember
Recursion memory = depth of the recursion.