DFS in-order, pre-order y post-order
Implemente los tres recorridos DFS de forma recursiva e iterativa con una pila explícita, y explique cuándo resulta útil cada orden.
DFS in-order, pre-order y post-order es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Tres órdenes de recorrido DFS
DFS en un árbol binario visita los nodos en uno de tres órdenes, según cuándo se procesa la raíz con respecto a sus hijos. Preorden: raíz → izquierda → derecha. Inorden: izquierda → raíz → derecha. Postorden: izquierda → derecha → raíz. Los nombres indican dónde se coloca la raíz en la secuencia. Comprender los tres es fundamental, porque distintos problemas requieren órdenes diferentes.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Recorrido preorden recursivo
En el preorden, el nodo actual se procesa antes que sus subárboles. Esto refleja la lectura natural de un árbol de arriba abajo y se utiliza para copiar árboles, serializarlos y evaluar expresiones prefijas. La implementación recursiva es muy breve, pero crea una pila de llamadas de profundidad O(h), donde h es la altura del árbol.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Recorrido inorden recursivo
El recorrido inorden visita el subárbol izquierdo, luego la raíz y después el subárbol derecho. En un árbol binario de búsqueda, el recorrido inorden siempre produce una secuencia ordenada; esta propiedad se utiliza en problemas como validar un BST, encontrar el k-ésimo elemento más pequeño y convertir un BST en un arreglo ordenado. Es el recorrido más importante que debe conocer para resolver problemas de BST.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Recorrido postorden recursivo
El recorrido postorden procesa ambos hijos antes que el nodo actual. Este orden ascendente desde las hojas es natural cuando el cálculo del padre depende de los resultados de sus hijos, por ejemplo, al calcular tamaños de subárboles, eliminar un árbol o evaluar un árbol de expresiones. La mayoría de los problemas de árboles que transmiten información hacia arriba utilizan una lógica postorden implícita.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Preorden iterativo con una pila
Para evitar los límites de profundidad de la recursión, implemente DFS de forma iterativa mediante una pila explícita. Para el preorden, coloque la raíz en la pila y, en cada iteración, extraiga un nodo, regístrelo y añada primero su hijo derecho y después el izquierdo (el derecho se añade primero para procesar antes el izquierdo). Esto imita el comportamiento LIFO de la pila de llamadas y es el enfoque habitual para árboles profundos, en los que fallaría el límite de recursión predeterminado de Python, que es de 1000.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Inorden iterativo con una pila
El inorden iterativo es algo más complicado. Utilice una pila y un puntero curr: avance hacia la izquierda todo lo posible, introduciendo cada nodo en la pila. Cuando ya no pueda avanzar más hacia la izquierda, extraiga un nodo, regístrelo y avance hacia la derecha. Este patrón —avanzar hacia la izquierda hasta encontrar null, extraer y procesar, y después avanzar hacia la derecha— es una técnica iterativa fundamental que aparece en problemas de iteradores de BST.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Postorden iterativo con dos pilas
El postorden iterativo tiene un truco ingenioso: ejecute un preorden modificado (raíz → derecha → izquierda) y recopile los resultados en orden inverso. Introduzca la raíz en la pila, extráigala y añádala al principio del resultado; después, introduzca primero el hijo izquierdo y luego el derecho. La inversión convierte raíz-derecha-izquierda en izquierda-derecha-raíz, que es exactamente el postorden. Como alternativa, utilice un puntero prev para realizar un seguimiento del último nodo visitado con una sola pila.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Cuándo elegir cada recorrido
Elegir el recorrido adecuado es un aspecto clave en las entrevistas. Utilice el preorden cuando necesite procesar un padre antes que sus hijos (serializar un árbol o copiar su estructura). Utilice el inorden en BST para aprovechar el ordenamiento. Utilice el postorden al calcular valores que dependen de ambos hijos (altura, diámetro o suma del subárbol). Se prefiere BFS para problemas de caminos mínimos y agrupación por niveles.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Recorrido de Morris: espacio O(1) en inorden
El recorrido de Morris consigue un espacio O(1) en inorden modificando temporalmente el árbol. Para cada nodo con un subárbol izquierdo, encuentre el predecesor inorden (el nodo situado más a la derecha del subárbol izquierdo) y enlace su puntero derecho de vuelta al nodo actual. Después de visitarlo, restaure el enlace. Esta técnica avanzada aparece en entrevistas de primer nivel cuando el entrevistador pregunta: «¿Puede hacerlo con un espacio adicional O(1)?»
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Reconstrucción del árbol a partir de recorridos
A partir de arreglos de preorden e inorden, puede reconstruir el árbol original. El primer elemento del preorden siempre es la raíz. Busque esa raíz en el arreglo inorden: todo lo que queda a su izquierda pertenece al subárbol izquierdo y todo lo que queda a su derecha, al subárbol derecho. Aplique este procedimiento de forma recursiva a los subarreglos. La complejidad temporal es O(n) si utiliza una búsqueda del índice en un mapa hash.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Resumen temporal y espacial de los recorridos
Los tres recorridos DFS tienen una complejidad temporal O(n), porque cada nodo se visita exactamente una vez. La complejidad espacial es O(h), donde h es la altura del árbol: O(log n) para árboles equilibrados y O(n) para árboles sesgados (debido a la pila de llamadas o a la pila explícita). Las implementaciones iterativas evitan el límite de recursión de Python, pero utilizan el mismo espacio asintótico. El recorrido de Morris consigue de forma única un espacio O(1) al reutilizar los punteros derechos del árbol.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: los tres órdenes de recorrido DFS (preorden, inorden y postorden) y cuándo elegir cada uno; las implementaciones recursivas e iterativas mediante una pila explícita; y la técnica de Morris con espacio O(1). A continuación, exploraremos cómo calcular el diámetro, la altura y el equilibrio de los árboles binarios.
Preguntas frecuentes
¿La lección «DFS in-order, pre-order y post-order» es gratis?
Sí — el texto completo de «DFS in-order, pre-order y post-order» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «DFS in-order, pre-order y post-order»?
Implemente los tres recorridos DFS de forma recursiva e iterativa con una pila explícita, y explique cuándo resulta útil cada orden. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «DFS in-order, pre-order y post-order»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Clase TreeNode y BFS por niveles
- DFS in-order, pre-order y post-order
- Diámetro, altura y árboles balanceados
- Suma de rutas y ancestro común más bajo