Sesión 32: Refuerzo y Evaluación de Árboles Binarios & BST#

Navegación rápida:

• ← Sesión 31: Evaluación — Stacks, Queues y Monotonic Stack
• Sesión 33: Evaluación — Grafos, BFS y Dijkstra →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_32.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión evaluamos el modelado y recorrido de jerarquías binarias en memoria Heap, combinando reconstrucción topológica determinista con análisis dinámico Post-Order (Bottom-Up). Consulta el Glosario Maestro y la Guía de Diagramas.

Recorrido Preorder como Identificador de Raíz#

• (a) En palabras simples (intuición): El director de una escuela que entra primero a la sala de conferencias antes de que entren los profesores y los alumnos. Su presencia te dice de inmediato quién es el líder de todo el grupo antes de mirar a los demás.
• (b) Definición técnica paso a paso: Secuencia de recorrido en profundidad (DFS) que visita los nodos en orden Raíz -> Izquierda -> Derecha. Para cualquier segmento contiguo que represente un subárbol, el primer elemento (preorder[pre_start]) es indiscutiblemente la raíz jerárquica de dicho subárbol.
• (c) Cómo funciona en Rust (memoria y tipos): Se lee el valor del slice mediante indexación directa inmutable preorder[pre_start], sin transferir propiedad ni clonar memoria física.
• (d) Error típico de Junior: Intentar deducir la raíz a partir de inorder; inorder mezcla la raíz entre los subárboles y no puede identificar cuál de los nodos es el ancestro principal.

Recorrido Inorder como Separador Topológico#

• (a) En palabras simples (intuición): Una cerca divisoria en un terreno. Cuando encuentras la cerca (la raíz), todo lo que está a la izquierda de la cerca pertenece al vecino del lado izquierdo, y todo lo que está a la derecha pertenece al vecino del lado derecho.
• (b) Definición técnica paso a paso: Recorrido DFS que visita en orden Izquierda -> Raíz -> Derecha. Al ubicar la posición de la raíz dentro de inorder (índice k), todos los elementos en el subrango [in_start..k-1] forman el subárbol izquierdo, y todos en [k+1..in_end] forman el subárbol derecho.
• (c) Cómo funciona en Rust (memoria y tipos): Los índices se mapean previamente en un std::collections::HashMap<i32, usize> en el Heap para localizar cualquier raíz en O(1) tiempo sin ejecutar búsquedas lineales.
• (d) Error típico de Junior: Utilizar .iter().position() o rebanados de vectores (&inorder[..k]) en cada llamada recursiva; esto genera una búsqueda O(N) y copias que degradan el algoritmo a O(N²).

Curvatura Local (Turning Point) vs Propagación Unilateral al Padre#

• (a) En palabras simples (intuición): Una carretera que sube una montaña, cruza el pico más alto (el nodo de curvatura) y baja por el otro lado hacia el valle. Un auto puede hacer ese viaje completo. Pero si un pueblo más arriba en la montaña te pide que construyas una carretera hacia allá, el auto no puede bifurcarse y subir al pueblo al mismo tiempo que baja por los dos lados; debe elegir solo una de las dos laderas.
• (b) Definición técnica paso a paso: En el problema del camino de suma máxima (LC 124), un camino válido en un árbol no puede pasar dos veces por el mismo nodo. En cada nodo u:
• Puede actuar como vértice o puente de curvatura: combinando ambas ramas (u.val + left_gain + right_gain). Este camino está completo y compite contra el récord global histórico.
• Pero al retornar un valor a su padre superior, solo puede ofrecer una rama unilateral: u.val + max(left_gain, right_gain).
• (c) Cómo funciona en Rust (memoria y tipos): Se mantiene una variable mutable externa global_max: &mut i32 en el Stack donde se evalúa la curvatura local, mientras que el valor de retorno de la función recursiva es únicamente la ganancia unilateral.
• (d) Error típico de Junior: Retornar val + left + right al padre; el compilador aceptará el tipo entero, pero el algoritmo producirá caminos inválidos en forma de "Y" o tenedor que violan la definición de camino simple.

Poda Voraz de Ganancias Negativas (max(0, gain))#

• (a) En palabras simples (intuición): Si alguien te ofrece una bolsa de dinero que contiene una deuda de 50 dólares (suma negativa), simplemente dices "no, gracias" y la dejas en el suelo. Cero dólares es mejor que perder 50.
• (b) Definición técnica paso a paso: Decisión voraz (Greedy Choice) en la propagación Post-Order donde, si la ganancia calculada de un subárbol izquierdo o derecho es menor que cero (gain < 0), se descarta reemplazándola por 0 mediante gain.max(0).
• (c) Cómo funciona en Rust (memoria y tipos): Se evalúa con let left_gain = max_gain(&n.left, global_max).max(0);, evitando que ramas tóxicas resten valor al camino acumulado.
• (d) Error típico de Junior: Sumar ciegamente el resultado de la llamada hija sin truncar en cero, perjudicando la suma global del camino.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Partición de Rangos en LC 105#

Sean dos secuencias de N elementos únicos: preorder e inorder. En cualquier llamada recursiva que opere sobre el segmento preorder[pre_start..=pre_end] e inorder[in_start..=in_end]:

1. La raíz es:
   root_val = preorder[pre_start]
2. Buscamos root_val en nuestra tabla hash:
   in_rootᵢdx = in_map[root_val]
3. El número exacto de nodos que pertenecen al subárbol izquierdo viene dado por la distancia en inorder:
   left_size = in_rootᵢdx - in_start
4. Delimitación rigurosa de los subrangos: - Subárbol Izquierdo: - En preorder: comienza en pre_start + 1 y abarca exactamente left_size elementos ⟹ [pre_start + 1 … pre_start + left_size]. - En inorder: abarca desde in_start hasta antes de la raíz ⟹ [in_start … in_rootᵢdx - 1]. - Subárbol Derecho: - En preorder: comienza justo después del bloque izquierdo ⟹ [pre_start + left_size + 1 … pre_end]. - En inorder: abarca desde justo después de la raíz ⟹ [in_rootᵢdx + 1 … in_end].

Como cada paso calcula límites aritméticos simples en O(1) y se efectúa exactamente una llamada recursiva por cada uno de los N nodos, la complejidad temporal es rigurosamente O(N) y no genera ninguna asignación redundante en el Heap.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Diagramas de Arquitectura#

• Gráfico SVG vectorial: ![Visualización del Día 32 y Memoria en Rust](../diagrams/sesiones/dia_32.svg)
• Código fuente del diagrama: Fuente Mermaid

Flujo de Ganancias Post-Order (Bottom-Up) en LC 124#

flowchart TD
    DFS["Entrar a nodo u con valor u.val"] --> L["left = max(0, dfs(u.left))"]
    DFS --> R["right = max(0, dfs(u.right))"]
    L & R --> CURV["Camino de Curvatura Local:<br/>current = u.val + left + right"]
    CURV --> REC["global_max = max(global_max, current)"]
    REC --> RET["Retornar ganancia al Padre:<br/>u.val + max(left, right)"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de build_tree_preorder_inorder(&[3, 9, 20, 15, 7], &[9, 3, 15, 20, 7]):

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame build_tree              |               | in_map: HashMap<i32, usize>          |
|   pre: &[i32] (ptr, len=5)    |               | { 9:0, 3:1, 15:2, 20:3, 7:4 }        |
|   in: &[i32] (ptr, len=5)     |               +--------------------------------------+
|   in_map: HashMap ------------+-------------->| Nodos creados:                       |
+-------------------------------+               | Box::new(TreeNode { val: 3, ... })   |
| Frame helper (Raíz 3)         |               |   left: Box(TreeNode { val: 9 })     |
|   pre_start: 0, pre_end: 4    |               |   right: Box(TreeNode { val: 20 })   |
|   in_start: 0, in_end: 4      |               |            left: Box(15)             |
|   root_val: 3, in_idx: 1      |               |            right: Box(7)             |
|   left_size: 1 - 0 = 1        |               +--------------------------------------+
+-------------------------------+

Paso 1: helper(pre: 0..4, in: 0..4) -> Crea nodo 3.
  - Subárbol izquierdo: helper(pre: 1..1, in: 0..0)
    root_val = 9, in_idx = 0, left_size = 0.
    Crea nodo 9. left_size=0 -> left=None, right=None. Retorna Box(9).
    nodo(3).left = Some(Box(9)).

  - Subárbol derecho: helper(pre: 2..4, in: 2..4)
    root_val = 20, in_idx = 3, in_start = 2. left_size = 3 - 2 = 1.
    Crea nodo 20.
    - Izq de 20: helper(pre: 3..3, in: 2..2) -> Crea Box(15).
    - Der de 20: helper(pre: 4..4, in: 4..4) -> Crea Box(7).
    nodo(20).left = Some(Box(15)), nodo(20).right = Some(Box(7)).
    nodo(3).right = Some(Box(20)).

Retorna Some(Box(3)) como raíz definitiva con propiedad única en el Heap.

4. Las 3 Trampas Clásicas en Entrevistas#

1. Inicializar global_max = 0 en LC 124: - Si el árbol contiene únicamente valores negativos (por ejemplo [-5, -2, -8]), cualquier suma de camino será estrictamente menor que cero. Si inicializas con 0, tu algoritmo responderá erróneamente 0. - Regla: Inicializar siempre con el valor mínimo representable: i32::MIN o float('-inf').
2. Propagar Ambas Ramas hacia Arriba: - Devolver al padre u.val + left + right. Un camino continuo no puede dividirse en dos hacia arriba y hacia abajo al mismo tiempo. Al padre se le ofrece estrictamente una sola rama: u.val + max(left, right).
3. Degradación Cuadrática O(N²) por Slicing en LC 105: - En Python o JavaScript, escribir build_tree(preorder[1:k], inorder[:k]) crea copias contiguas de memoria en cada llamada recursiva. En Rust o en cualquier lenguaje de alto rendimiento, se deben pasar siempre punteros a slices o índices de rango.

5. Implementación Canónica en Rust + Comparativa con Python#

Implementación Canónica en Rust (practica-rust/dia_32.rs)#

//! Día 32: Refuerzo y Evaluación de Árboles Binarios & BST en Rust.
use std::collections::HashMap;

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Box<TreeNode>>,
    pub right: Option<Box<TreeNode>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        Self { val, left: None, right: None }
    }
}

/// LeetCode 105: Reconstrucción en O(N) tiempo y O(N) espacio auxiliar con HashMap.
pub fn build_tree_preorder_inorder(preorder: &[i32], inorder: &[i32]) -> Option<Box<TreeNode>> {
    if preorder.is_empty() || inorder.is_empty() || preorder.len() != inorder.len() {
        return None;
    }

    let mut in_map = HashMap::with_capacity(inorder.len());
    for (idx, &val) in inorder.iter().enumerate() {
        in_map.insert(val, idx);
    }

    fn helper(
        preorder: &[i32],
        pre_start: usize,
        pre_end: usize,
        in_start: usize,
        in_end: usize,
        in_map: &HashMap<i32, usize>,
    ) -> Option<Box<TreeNode>> {
        if pre_start > pre_end || in_start > in_end {
            return None;
        }

        let root_val = preorder[pre_start];
        let &in_root_idx = in_map.get(&root_val)?;
        if in_root_idx < in_start || in_root_idx > in_end {
            return None;
        }

        let left_size = in_root_idx - in_start;
        let mut root = Box::new(TreeNode::new(root_val));

        if left_size > 0 {
            root.left = helper(
                preorder,
                pre_start + 1,
                pre_start + left_size,
                in_start,
                in_root_idx - 1,
                in_map,
            );
        }

        if in_root_idx < in_end {
            root.right = helper(
                preorder,
                pre_start + left_size + 1,
                pre_end,
                in_root_idx + 1,
                in_end,
                in_map,
            );
        }

        Some(root)
    }

    helper(preorder, 0, preorder.len() - 1, 0, inorder.len() - 1, &in_map)
}

/// LeetCode 124: Camino de Suma Máxima vía DFS Post-Order en O(N) tiempo.
pub fn max_path_sum(root: &Option<Box<TreeNode>>) -> i32 {
    if root.is_none() {
        return 0;
    }

    let mut global_max = i32::MIN;

    fn max_gain(node: &Option<Box<TreeNode>>, global_max: &mut i32) -> i32 {
        let n = match node {
            Some(boxed) => boxed,
            None => return 0,
        };

        let left_gain = max_gain(&n.left, global_max).max(0);
        let right_gain = max_gain(&n.right, global_max).max(0);

        let current_path_sum = n.val + left_gain + right_gain;
        if current_path_sum > *global_max {
            *global_max = current_path_sum;
        }

        n.val + left_gain.max(right_gain)
    }

    max_gain(root, &mut global_max);
    global_max
}

Implementación Canónica en Python (practica/dia_32_trees_traversals_max_path.py)#

from typing import Dict, List, Optional

class TreeNode:
    def __init__(self, val: int = 0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_tree_preorder_inorder(preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
    """LC 105: Reconstrucción O(N) con Hash Map de índices sin slicing de listas."""
    in_map = {val: idx for idx, val in enumerate(inorder)}

    def helper(pre_start: int, pre_end: int, in_start: int, in_end: int) -> Optional[TreeNode]:
        if pre_start > pre_end or in_start > in_end:
            return None

        root_val = preorder[pre_start]
        in_root_idx = in_map[root_val]
        left_size = in_root_idx - in_start

        root = TreeNode(root_val)
        root.left = helper(pre_start + 1, pre_start + left_size, in_start, in_root_idx - 1)
        root.right = helper(pre_start + left_size + 1, pre_end, in_root_idx + 1, in_end)
        return root

    return helper(0, len(preorder) - 1, 0, len(inorder) - 1)

def max_path_sum(root: Optional[TreeNode]) -> int:
    """LC 124: Camino de Suma Máxima con poda negativa en O(N) tiempo."""
    max_sum = float("-inf")

    def max_gain(node: Optional[TreeNode]) -> float:
        nonlocal max_sum
        if not node:
            return 0.0

        left_gain = max(0.0, max_gain(node.left))
        right_gain = max(0.0, max_gain(node.right))

        current_path = node.val + left_gain + right_gain
        if current_path > max_sum:
            max_sum = current_path

        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return int(max_sum)

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 105 — Construct Binary Tree from Preorder and Inorder Traversal (Medium): - Resuelve el problema aplicando la partición de rangos de índices con HashMap.
2. LeetCode 106 — Construct Binary Tree from Inorder and Postorder Traversal (Medium): - Variante complementaria: la raíz se extrae del final de Postorder.
3. LeetCode 124 — Binary Tree Maximum Path Sum (Hard): - Domina la técnica de curvatura local frente a retorno unilateral.
4. LeetCode 543 — Diameter of Binary Tree (Easy): - Práctica fundamental del cálculo de profundidad y diámetro en Post-Order.

8. Tarea en Papel para Hoy#

Toma una hoja y tu lápiz:

1. Dados preorder = [1, 2, 4, 5, 3], inorder = [4, 2, 5, 1, 3]: - Construye la tabla de llamadas recursivas con los rangos pre_start..pre_end e in_start..in_end. - Dibuja el árbol final resultante.
2. Sobre ese mismo árbol: - Asigna a los nodos los valores: node(1) = -10, node(2) = 9, node(3) = 20, node(4) = 15, node(5) = 7. - Traza a mano el algoritmo de max_path_sum anotando la ganancia que cada nodo retorna a su padre y el valor del récord global en cada visita Post-Order.

Navegación:

• ← Volver a Sesión 31: Evaluación — Stacks, Queues y Monotonic Stack
• Avanzar a Sesión 33: Evaluación — Grafos, BFS y Dijkstra →