Sesión 24: CTCI Capítulo 4 — Validate BST (4.5) y Check Balanced (4.4)#

Navegación rápida:

• ← Sesión 23: CTCI Ch4 — Árboles, Recorridos y Minimal Tree
• Sesión 25: CTCI Ch4 — Successor y Lowest Common Ancestor →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_24.rs

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

En esta sesión abordamos las dos preguntas de validación estructural más frecuentes en entrevistas de árboles: verificar si un árbol satisface la propiedad de orden global de un BST y confirmar si está balanceado en altura. Consulta el Glosario Maestro y la Guía de Diagramas.

Invariante Global de un BST (Condición Hereditaria)#

• (a) En palabras simples (intuición): En una empresa organizada, el sueldo de cualquier empleado de una sucursal de bajo costo no puede superar al del director general corporativo, sin importar a cuántos jefes intermedios reporte.
• (b) Definición técnica paso a paso: Propiedad matemática estricta que exige que para todo nodo ancestral A, absolutamente todos los descendientes en su subárbol izquierdo deben tener valores menores que A.val, y todos los descendientes en su subárbol derecho deben tener valores mayores que A.val.
• (c) Cómo funciona en Rust (memoria y tipos): Se valida pasando límites opcionales (Option<i64>, Option<i64>) en la recursión o comprobando que la secuencia In-Order no decrezca.
• (d) Error típico de Junior: Evaluar únicamente la condición local node.left < node < node.right. Un nodo puede ser mayor que su padre inmediato pero menor que su abuelo ancestral, violando la invariante global sin ser detectado localmente.

Propagación Descendente de Cotas Abiertas ((min_bound, max_bound))#

• (a) En palabras simples (intuición): Conducir un camión por un túnel que se va haciendo cada vez más angosto en cada curva. Al doblar a la izquierda, la pared derecha se acerca; al doblar a la derecha, la pared izquierda se acerca. Si el camión roza cualquier pared, queda atascado.
• (b) Definición técnica paso a paso: Técnica top-down donde cada llamada recursiva recibe un intervalo abierto permitido (low, high). Al descender al hijo izquierdo, el valor del padre se convierte en la nueva cota superior (high gets val). Al descender al hijo derecho, el valor del padre se convierte en la nueva cota inferior (low gets val).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con min_bound: Option<i64> y max_bound: Option<i64> para evitar desbordamientos aritméticos con i32::MIN y i32::MAX.
• (d) Error típico de Junior: Usar comparaciones con menor o igual (≤) en lugar de menor estricto (<), permitiendo duplicados en un BST que no los tolera.

In-Order Monótono Estricto#

• (a) En palabras simples (intuición): Subir una escalera donde cada peldaño debe estar obligatoriamente a mayor altura que el anterior. Si pisas un peldaño a la misma altura o más bajo, la escalera está defectuosa.
• (b) Definición técnica paso a paso: Propiedad por la cual recorrer un BST válido en orden In-Order (Left -> Root -> Right) produce una secuencia de valores estrictamente creciente:

• (c) Cómo funciona en Rust (memoria y tipos): Mantiene una variable mutable prev: &mut Option<i32> a través de la recursión. Si node.val <= prev, la función retorna false inmediatamente.
• (d) Error típico de Junior: Asignar a prev el valor -1 o un entero arbitrario como centinela inicial, fallando ante árboles que contienen valores negativos válidos.

Árbol Balanceado (Criterio AVL: |h_{izq} - h_{der}| ≤ 1)#

• (a) En palabras simples (intuición): Una balanza de dos platillos. Puede inclinarse un poquito hacia un lado por un objeto pequeño, pero si la diferencia entre ambos brazos es de dos o más pisos, la balanza se desmorona.
• (b) Definición técnica paso a paso: Un árbol binario está balanceado si y solo si, para cada uno de los nodos del árbol, la diferencia absoluta entre la altura de su subárbol izquierdo y la altura de su subárbol derecho es a lo sumo 1:

• (c) Cómo funciona en Rust (memoria y tipos): Se computa mediante un recorrido Post-Order DFS que calcula alturas de abajo hacia arriba (bottom-up).
• (d) Error típico de Junior: Asumir que un árbol está balanceado solo porque la altura del subárbol izquierdo de la raíz principal y la del derecho difieren en 1, ignorando que un subárbol interno profundo puede estar completamente desbalanceado.

Post-Order DFS Bottom-Up con Centinela / Cortocircuito Temprano#

• (a) En palabras simples (intuición): Una alarma de incendio en un edificio de oficinas. En cuanto un sensor del sótano detecta humo, hace sonar la alarma general y todos evacúan de inmediato, sin esperar a que el humo suba piso por piso hasta el ático.
• (b) Definición técnica paso a paso: Algoritmo recursivo que calcula la altura de los subárboles de abajo hacia arriba. Si un hijo detecta que está desbalanceado, aborta inmediatamente retornando un centinela de error (o Err(()) en Rust), propagando el fallo hacia la raíz sin calcular alturas innecesarias.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa elegantemente con el operador ? sobre tipos Result<usize, ()>: si una rama retorna Err(()), el operador propaga el error instantáneamente.
• (d) Error típico de Junior: Llamar a una función auxiliar height(node) dentro de cada nodo en un enfoque Top-Down, recorriendo los mismos nodos una y otra vez y degradando el tiempo a O(N²).

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

La Falacia Local vs la Invariante Global#

¿Por qué una simple comprobación local left.val < node.val < right.val es uno de los errores más comunes en entrevistas? Consideremos el siguiente árbol binario:

           10
         /    \
        5      15
              /  \
            [6]   20

Analicemos la comprobación local nodo por nodo:

1. En el nodo 5: No tiene hijos → Válido.
2. En el nodo 15: Su hijo izquierdo es 6 (6 < 15) y su hijo derecho es 20 (20 > 15) → Localmente parece válido.
3. En la raíz 10: Su hijo izquierdo es 5 (5 < 10) y su hijo derecho es 15 (15 > 10) → Localmente parece válido.

Sin embargo, ¡el árbol NO es un BST! El nodo 6 reside en el subárbol derecho de la raíz 10. Por la invariante global de un BST, todos los nodos a la derecha de 10 deben ser estrictamente mayores que 10. Como 6 < 10, la estructura está corrupta.

La Matemática de la Propagación de Cotas (low, high)#

Para validar correctamente en una sola pasada O(N), cada llamada recursiva viaja con un túnel de restricciones abiertas:

1. Raíz: No tiene restricciones ancestrales:
   (low = -∞, high = +∞)
2. Descenso a la Izquierda: Todo nodo en el subárbol izquierdo debe ser menor que el padre actual. Por tanto, el valor del padre actual se convierte en la nueva cota superior:
   (low_{hijo} = low_{padre}, high_{hijo} = padre.val)
3. Descenso a la Derecha: Todo nodo en el subárbol derecho debe ser mayor que el padre actual. Por tanto, el valor del padre se convierte en la nueva cota inferior:
   (low_{hijo} = padre.val, high_{hijo} = high_{padre})

Aplicando esto al árbol trampa:

• En la raíz 10: (-∞, +∞) ⟹ 10 ∈ (-∞, +∞) → Válido.
• Al bajar a la derecha hacia 15: Cota se actualiza a (10, +∞). Como 15 ∈ (10, +∞) → Válido.
• Al bajar a la izquierda de 15 hacia 6: Cota se actualiza a (10, 15).
• Al evaluar el nodo 6: ¿10 < 6 < 15?

¡FALSO! 6 ≤ 10. El algoritmo detecta la violación y aborta en O(1).

Check Balanced: Por Qué Top-Down es O(N²) y Bottom-Up es O(N)#

• Enfoque Top-Down Ingenuo:

  # Ineficiente: O(N^2)
  def is_balanced(node):
      if not node: return True
      if abs(height(node.left) - height(node.right)) > 1: return False
      return is_balanced(node.left) and is_balanced(node.right)

Para la raíz, height() recorre los N nodos del árbol. Para los dos hijos de la raíz, height() vuelve a recorrer N - 1 nodos. En un árbol lineal, el trabajo total es:

• Enfoque Bottom-Up (Post-Order con Centinela):

Comenzamos desde las hojas y subimos hacia la raíz. Cada nodo recibe las alturas ya calculadas de sus dos hijos directos. Calcula su propia altura en tiempo constante: 1 + max(h_{izq}, h_{der}). Comprueba la diferencia de alturas en O(1). Cada nodo se visita exactamente una sola vez ⟹ O(N) tiempo lineal estricto.

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 24 y Memoria en Rust](../diagrams/sesiones/dia_24.svg)
• Código fuente del diagrama: Fuente Mermaid

Detección de Violación de Cotas y Chequeo Bottom-Up#

flowchart TD
    subgraph BST["Validación con Túnel de Cotas (low, high)"]
        R["10 (low=-inf, high=+inf)"] --> L["5 (low=-inf, high=10)"]
        R --> RT["15 (low=10, high=+inf)"]
        RT --> ERR["[6] (low=10, high=15) -> ¡VIOLACIÓN: 6 <= 10!"]
        RT --> OK["20 (low=15, high=+inf)"]
    end
    subgraph BAL["Check Balanced Bottom-Up"]
        H3["Nodo 3: h=1"] --> H2["Nodo 2: h=1+1=2"]
        H0["None: h=0"] --> H1["Nodo 1: h_izq=2, h_der=0 -> Diff=2 > 1 -> ¡Err(())!"]
        H2 --> H1
    end

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

Ejecución de is_balanced sobre 1 -> 2 -> 3 (cadena izquierda en Heap):

STACK CALL FRAMES                                HEAP
+------------------------------------+          +--------------------------------------+
| check_height(Node 1)               |          | Nodo 1: left -> 0x2000, right -> None|
|   espera resultado de n.left       |          +--------------------------------------+
+------------------------------------+                             |
| check_height(Node 2 en 0x2000)     | <---------------------------+
|   espera resultado de n.left       |          +--------------------------------------+
+------------------------------------+          | Nodo 2: left -> 0x3000, right -> None|
| check_height(Node 3 en 0x3000)     |          +--------------------------------------+
|   left = None (Ok(0))              |                             |
|   right = None (Ok(0))             | <---------------------------+
|   diff = |0 - 0| = 0 <= 1          |          +--------------------------------------+
|   retorna Ok(1 + max(0,0)) = Ok(1) |          | Nodo 3: left -> None, right -> None  |
+------------------------------------+          +--------------------------------------+

Retorno de llamada de Node 3:
- Frame de Node 2 reanuda:
  left_h = 1
  right_h = check_height(None) = 0
  diff = |1 - 0| = 1 <= 1
  retorna Ok(1 + max(1, 0)) = Ok(2)

Retorno de llamada de Node 2:
- Frame de Node 1 reanuda:
  left_h = 2
  right_h = check_height(None) = 0
  diff = |2 - 0| = 2 > 1  <-- ¡DESBALANCE DETECTADO!
  retorna Err(()) inmediatamente mediante operador ?

La función is_balanced comprueba .is_ok() y retorna false en O(N) sin explorar subárboles redundantes.

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

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

//! Día 24: Validate BST (CTCI 4.5, LeetCode 98) y Check Balanced (CTCI 4.4, LeetCode 110) en Rust.
//! Compilable y verificable con `rustc --test`.

#[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 }
    }
}

/// CTCI 4.5 / LeetCode 98: Validación con cotas abiertas (Option<i64>) en O(N).
pub fn is_valid_bst_bounds(root: &Option<Box<TreeNode>>) -> bool {
    fn validate(node: &Option<Box<TreeNode>>, min_bound: Option<i64>, max_bound: Option<i64>) -> bool {
        match node {
            None => true,
            Some(n) => {
                let val = n.val as i64;
                if let Some(min) = min_bound {
                    if val <= min { return false; }
                }
                if let Some(max) = max_bound {
                    if val >= max { return false; }
                }
                validate(&n.left, min_bound, Some(val)) && validate(&n.right, Some(val), max_bound)
            }
        }
    }
    validate(root, None, None)
}

/// Validación de BST mediante recorrido In-Order monótono.
pub fn is_valid_bst_inorder(root: &Option<Box<TreeNode>>) -> bool {
    fn helper(node: &Option<Box<TreeNode>>, prev: &mut Option<i32>) -> bool {
        match node {
            None => true,
            Some(n) => {
                if !helper(&n.left, prev) { return false; }
                if let Some(p) = *prev {
                    if n.val <= p { return false; }
                }
                *prev = Some(n.val);
                helper(&n.right, prev)
            }
        }
    }
    let mut prev = None;
    helper(root, &mut prev)
}

/// CTCI 4.4 / LeetCode 110: Chequeo de árbol balanceado Bottom-Up en O(N).
pub fn is_balanced(root: &Option<Box<TreeNode>>) -> bool {
    fn check_height(node: &Option<Box<TreeNode>>) -> Result<usize, ()> {
        match node {
            None => Ok(0),
            Some(n) => {
                let left_h = check_height(&n.left)?;
                let right_h = check_height(&n.right)?;

                if left_h.abs_diff(right_h) > 1 {
                    Err(())
                } else {
                    Ok(1 + left_h.max(right_h))
                }
            }
        }
    }
    check_height(root).is_ok()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_bst_validation() {
        // Árbol válido: 2 -> [1, 3]
        let mut root = TreeNode::new(2);
        root.left = Some(Box::new(TreeNode::new(1)));
        root.right = Some(Box::new(TreeNode::new(3)));
        let tree = Some(Box::new(root));

        assert!(is_valid_bst_bounds(&tree));
        assert!(is_valid_bst_inorder(&tree));
        assert!(is_balanced(&tree));
    }

    #[test]
    fn test_ancestor_violation() {
        // Árbol inválido con violación de abuelo:
        //      10
        //     /  \
        //    5    15
        //        /  \
        //      [6]   20
        let mut root = TreeNode::new(10);
        root.left = Some(Box::new(TreeNode::new(5)));
        let mut right = TreeNode::new(15);
        right.left = Some(Box::new(TreeNode::new(6)));
        right.right = Some(Box::new(TreeNode::new(20)));
        root.right = Some(Box::new(right));
        let tree = Some(Box::new(root));

        assert!(!is_valid_bst_bounds(&tree));
        assert!(!is_valid_bst_inorder(&tree));
    }
}

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

from typing import Optional

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

def is_valid_bst_bounds(
    root: Optional[TreeNode],
    low: float = float("-inf"),
    high: float = float("inf")
) -> bool:
    """CTCI 4.5 / LeetCode 98: Validación por cotas en O(N)."""
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (
        is_valid_bst_bounds(root.left, low, root.val)
        and is_valid_bst_bounds(root.right, root.val, high)
    )

def is_balanced(root: Optional[TreeNode]) -> bool:
    """CTCI 4.4 / LeetCode 110: Bottom-Up con centinela -1 en O(N)."""
    def _check(node: Optional[TreeNode]) -> int:
        if not node:
            return 0
        left_h = _check(node.left)
        if left_h == -1: return -1
        right_h = _check(node.right)
        if right_h == -1: return -1

        if abs(left_h - right_h) > 1:
            return -1
        return 1 + max(left_h, right_h)

    return _check(root) != -1

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Comprobación Ingenua de Hijos Locales: - Solo comparar el nodo con sus dos hijos inmediatos (left < node < right) dejará pasar árboles gravemente corruptos donde un descendiente de tercer nivel contradice a su abuelo ancestral.
2. Desbordamiento de Enteros en Límites Extremos: - Si un árbol contiene nodos con valor i32::MAX o i32::MIN y tus límites son de tipo i32: hacer comparaciones o sumas/restas de límites causará desbordamiento aritmético (integer overflow). Usa siempre Option<i64> o centinelas opcionales Option<T>.
3. Recalcular Alturas Repetidamente en Check Balanced: - Invocar una función separada height(node) dentro de cada nodo crea un algoritmo cuadrático O(N²). La altura y la validación de balance deben devolverse simultáneamente de abajo hacia arriba en O(N).

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

let left_h = check_height(&n.left)?;

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

1. LeetCode 98 — Validate Binary Search Tree (Medium): - Validación formal de BST mediante cotas e In-Order.
2. LeetCode 110 — Balanced Binary Tree (Easy): - Chequeo de balanceo Bottom-Up en O(N) con centinela.
3. LeetCode 501 — Find Mode in Binary Search Tree (Easy): - Aprovechamiento del recorrido In-Order de un BST para contar frecuencias consecutivas sin memoria auxiliar O(1).

8. Tarea en Papel para Hoy#

Toma una hoja de papel y dibuja el siguiente árbol binario: Raíz = 20, Izq = 10, Der = 30, Izq de 30 = 25, Der de 30 = 35, Der de 10 = 22.

1. Aplica a mano el algoritmo de Propagación de Cotas (low, high) comenzando en la raíz con (-∞, +∞).
2. Anota el intervalo que recibe cada nodo al descender.
3. Identifica en qué nodo exacto se detona la violación de la invariante del BST y por qué.
4. Calcula a mano el balanceo de alturas con el método Bottom-Up y determina si el árbol está balanceado.

Navegación:

• ← Volver a Sesión 23: CTCI Ch4 — Árboles, Recorridos y Minimal Tree
• Avanzar a Sesión 25: CTCI Ch4 — Successor y Lowest Common Ancestor →