tree - propiedades - ¿Cuál es la complejidad temporal del recorrido de los árboles?

ejemplos de arboles binarios

Question

¿Cuál es la complejidad temporal del recorrido del árbol? Estoy seguro de que debe ser obvio, pero mi pobre cerebro no puede resolverlo ahora mismo.

Answer 1

¿No sería eso n para un árbol con n nodos?

Usted visita cada árbol de una vez, ¿no? Así que diría que es lineal.

Answer 2

Depende del tipo de recorrido que esté realizando y del algoritmo, pero normalmente sería O (n) donde n es el número total de nodos en el árbol. La implementación recursiva canónica del primer recorrido de profundidad consumirá memoria (en la pila) en el orden del nivel más profundo, que en un árbol equilibrado sería log (n).