¿Cuál es la complejidad espacial de un DFS recursivo en un árbol binario de altura h?
Opciones
- O(1), porque no se reserva memoria extra
- O(h) por el call stack de la recursión (Opción correcta)
- O(n²), porque cada nodo se visita dos veces
- O(log h) por la profundidad del call stack
Respuesta
O(h) por el call stack
Por qué
El DFS recursivo mantiene un frame del call stack por cada nodo del camino actual desde la raíz. El camino más largo tiene h nodos, así que la memoria es O(h).
En un árbol balanceado h ≈ log n; en uno totalmente desequilibrado h = n.
BFS en cambio mantiene un nivel entero en su cola: O(anchura).
Recuerda
Memoria de la recursión = profundidad de la recursión.