Semanas 9 y 10 Arboles

Semanas 9 y 10: Árboles

Objetivo

Dominar DFS, BFS y recursión sobre árboles binarios, incluyendo validación de BST, búsqueda de ancestro común y construcción desde recorridos.

Problemas Completados

Problema	Patrón	Función	Tests
Maximum Depth of Binary Tree	DFS con retorno	max_depth	2
Invert Binary Tree	DFS con mutación	invert_tree	1
Diameter of Binary Tree	DFS con acumulador	diameter_of_binary_tree	1
Balanced Binary Tree	DFS con centinela	is_balanced	2
Same Tree	DFS emparejado	is_same_tree	2
Subtree of Another Tree	DFS + comparación	is_subtree	2
Binary Tree Level Order Traversal	BFS por niveles	level_order	1
Validate Binary Search Tree	DFS con límites	is_valid_bst	3
Lowest Common Ancestor of a BST	Búsqueda guiada por BST	lowest_common_ancestor_bst	2
Construct Binary Tree from Preorder and Inorder	División recursiva	build_tree_preorder_inorder	2
Kth Smallest Element in a BST	Inorder iterativo	kth_smallest_bst	2
Binary Tree Right Side View	BFS por niveles	right_side_view	2
Path Sum	DFS con objetivo restante	has_path_sum	2
Path Sum II	DFS con backtracking	path_sum_ii	2
Serialize and Deserialize Binary Tree	Codificación por niveles	serialize_tree, deserialize_tree	2
Construct Binary Tree from Inorder and Postorder	División recursiva	build_tree_inorder_postorder	2

Ideas Clave

DFS con Retorno

Se usa cuando cada nodo necesita calcular algo a partir de sus hijos.

Ejemplos:

• max_depth
• diameter_of_binary_tree
• is_balanced

DFS con Acumulador

En diameter_of_binary_tree, cada llamada devuelve altura, pero actualiza el mejor diámetro visto.

Invariante:

• La altura sube hacia el padre.
• El diámetro se calcula como left_height + right_height.

BFS por Niveles

En level_order, cada iteración procesa exactamente el tamaño actual de la cola.

Invariante:

• Los nodos en cola al inicio del ciclo pertenecen al mismo nivel.

Validación de BST

Cada nodo hereda límites estrictos desde sus ancestros.

Invariante:

• Todo nodo izquierdo debe ser menor que el límite superior.
• Todo nodo derecho debe ser mayor que el límite inferior.
• No basta comparar solo contra el padre.

Construcción desde Recorridos

En build_tree_preorder_inorder:

• Preorder da la raíz.
• Inorder indica cuántos nodos pertenecen al subárbol izquierdo y derecho.
• Un HashMap de índices evita buscar la raíz en O(n) cada vez.

La variante build_tree_inorder_postorder usa la misma idea, pero toma la raíz desde el final de postorder.

Inorder en BST

En kth_smallest_bst, un recorrido inorder visita los valores de menor a mayor.

Invariante:

• El stack contiene ancestros pendientes.
• Cada pop produce el siguiente valor ordenado.
• Si k sale del rango, la respuesta es None.

Path Sum

has_path_sum y path_sum_ii solo aceptan rutas raíz-hoja.

Invariante:

• Cada llamada resta el valor actual del objetivo restante.
• Una suma intermedia no cuenta si el nodo todavía tiene hijos.
• En path_sum_ii, el camino se clona solo cuando una hoja completa coincide.

Serialización por Niveles

serialize_tree convierte el árbol a una representación compacta por niveles usando # para hijos ausentes.

Ventajas:

• Es fácil de inspeccionar en tests.
• Reutiliza el helper tree_from_level_order para reconstruir.
• Evita guardar None finales que no cambian la estructura.

Representación en Rust

Se usó:

Option<Rc<RefCell<TreeNode>>>

Razón:

• Rc permite compartir referencias a nodos.
• RefCell permite mutación interior controlada.
• Esta representación es común en ejercicios de árboles con Rust.

Errores Comunes

• Comparar BST solo contra el padre.
• Olvidar trim de None al serializar por niveles.
• Confundir altura en nodos con diámetro en aristas.
• No clonar enlaces Rc antes de pasarlos a funciones recursivas.
• Recalcular índices de inorder sin mapa auxiliar.

Verificación

cargo test

Resultado al cerrar el bloque:

385 passed; 0 failed

Siguiente Bloque

El siguiente bloque recomendado es:

• Grafos.
• DFS/BFS en matriz.
• Componentes conectados.
• Ordenamiento topológico.
• Union Find.

Primeros problemas sugeridos:

• Number of Islands.
• Clone Graph.
• Max Area of Island.
• Course Schedule.
• Rotting Oranges.