Si hallas algún problema en tu código o proyecto, recuerda probar siempre en un entorno de testing antes subir el código al proyecto final.
Solución:
Las direcciones se eliminan de la pila al regresar. Este espacio se reutiliza al realizar una nueva llamada desde un nivel más cercano a la raíz. Entonces, el número máximo de direcciones de memoria en la pila al mismo tiempo es la altura del árbol.
En mi humilde opinión, debe tratar la complejidad del espacio como O(n) en lugar de. Al tratar con complejidades de espacio y tiempo en la notación Big O, siempre tratamos de dar el valor de complejidad en función del número de elementos de entrada, que es n en este caso.
Además, si considera los casos de un árbol binario sesgado a la derecha o un binario sesgado a la izquierda, entonces encontrará esto O(n) complejidad del espacio como adecuada. Eche un vistazo a los siguientes casos de árbol binario sesgado a la derecha:
1
/
2
/
3
Número de nodos, n = 3
Número de marcos de pila necesarios en el recorrido recursivo = 3
1
/
2
/
3
/
4
/
Número de nodos, n = 4
Número de marcos de pila requeridos en el recorrido recursivo = 4
Entonces puedes concluir que O(n) es una complejidad de espacio adecuada en el peor de los casos con la estructura de árbol. En todos los demás casos/tipos de árboles, el número de marcos de pila necesarios siempre será inferior a n. Y así es como expresamos las complejidades. El espacio real ocupado por todos los casos posibles siempre debe ser menor o igual que la función representada.
Asimismo, en todos los casos siempre será O(h) <= O(n). Así que pensando en la complejidad del espacio como O(n) simplemente nos da una forma uniforme de pensar en términos de número de entrada de elementos. Aunque, O(h) la complejidad del espacio es igualmente correcta debido a las razones mencionadas por @StefanHaustein en su respuesta.
Recuerda que tienes la capacidad de agregar una reseña .