Sesión 27: CTCI Capítulo 4 — Check Subtree (4.10) y Paths with Sum (4.12)#

Navegación rápida:

• ← Sesión 26: CTCI Ch4 — Topological Sort y Build Order
• Sesión 28: Grokking Ch7 — Dijkstra y Consolidación Semana 4 →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_27.rs

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

En esta sesión abordamos dos de los problemas más elegantes de combinación de técnicas: verificar la identidad estructural de subárboles y aplicar la técnica de sumas de prefijo con backtracking sobre estructuras arbóreas. Consulta el Glosario Maestro y la Guía de Diagramas.

Subárbol Idéntico (Check Subtree / Structural & Value Identity)#

• (a) En palabras simples (intuición): Tener una casa grande y una maqueta pequeña de una habitación. Buscas si existe alguna habitación dentro de la casa grande que tenga exactamente los mismos muebles, el mismo color de paredes y las mismas puertas en las mismas posiciones que la maqueta.
• (b) Definición técnica paso a paso: Un árbol binario T₂ es un subárbol idéntico de T₁ si existe algún nodo N ∈ T₁ tal que el subárbol con raíz en N sea idéntico en valores y en topología a T₂ (incluyendo todas sus hojas y punteros nulos terminales).
• (c) Cómo funciona en Rust (memoria y tipos): Se compara mediante una función recursiva is_same_tree(p, q) que evalúa igualdad de valor y recurre en left y right sobre Option<Box<TreeNode>>.
• (d) Error típico de Junior: Confundir "contener los mismos valores" con "subárbol idéntico". Si T₂ termina en una hoja pero el nodo correspondiente en T₁ tiene hijos adicionales hacia abajo, T₂ no es un subárbol idéntico; es solo un sub-grafo parcial.

Serialización Pre-Order con Centinelas Nulos (#) y Delimitadores#

• (a) En palabras simples (intuición): Describir un árbol por teléfono sin dibujar. Si solo dices "uno, dos", quien te escucha no sabe si el dos es el hijo izquierdo o el derecho. Pero si dices "uno, izquierda nada, derecha dos", la estructura queda perfectamente clara y sin ambigüedades.
• (b) Definición técnica paso a paso: Representación de un árbol binario como una cadena de texto única e inequívoca mediante recorrido Pre-Order (Root -> Left -> Right), donde cada puntero nulo se codifica explícitamente con un símbolo centinela (como #) y cada nodo se encierra entre delimitadores (como comas ,).
• (c) Cómo funciona en Rust (memoria y tipos): Escribe sobre un String en el Heap mediante out.push_str(",#") o out.push_str(&val.to_string()). Permite resolver el problema de subárbol buscando subcadenas con algoritmos como KMP en O(N + M).
• (d) Error típico de Junior: Omitir los marcadores nulos # o los delimitadores ,. Sin marcadores nulos, un árbol con 1 -> right 2 y otro con 1 -> left 2 producen la misma cadena 1, 2, generando falsos positivos.

Paths with Sum (Caminos Descendentes con Suma Objetivo - CTCI 4.12)#

• (a) En palabras simples (intuición): Caminar cuesta abajo por los senderos de una colina bifurcada. Cada paso que das suma un desnivel. Quieres contar cuántos tramos continuos de bajada suman exactamente un desnivel de 8 metros, sin importar dónde comenzaste a caminar ni dónde terminaste.
• (b) Definición técnica paso a paso: Problema que consiste en contar el número de caminos que descienden en línea recta (de padre a descendiente) cuya suma de valores es igual a target_sum. El camino no necesita empezar en la raíz ni terminar en una hoja.
• (c) Cómo funciona en Rust (memoria y tipos): Se resuelve óptimamente en O(N) combinando un recorrido DFS con una tabla hash de sumas de prefijo (HashMap<i64, usize>).
• (d) Error típico de Junior: Usar fuerza bruta iniciando un recorrido recursivo desde cada uno de los nodos del árbol, lo cual dispara la complejidad temporal a O(N²) o O(N log N).

Prefix Sum en Árboles (S_{actual} - S_{previo} = target)#

• (a) En palabras simples (intuición): Si tu odómetro marca 100 km al salir de casa y marca 180 km al llegar a tu destino, sabes con certeza absoluta que el viaje duró 80 km sin necesidad de medir cada tramo intermedio (180 - 100 = 80).
• (b) Definición técnica paso a paso: Principio algebraico donde la suma de cualquier camino entre un ancestro A y un descendiente D equivale a la diferencia de sus sumas acumuladas desde la raíz:

Al llegar al nodo D, consultamos en una tabla hash cuántos ancestros previos tuvieron una suma acumulada igual a S_D - target.

• (c) Cómo funciona en Rust (memoria y tipos): Consultar prefix_counts.get(&(current_sum - target)) devuelve la cantidad de caminos válidos en tiempo constante O(1).
• (d) Error típico de Junior: Olvidar que las sumas pueden ser negativas, lo que impide asumir monotonicidad creciente en las sumas acumuladas.

Backtracking sobre Tabla Hash#

• (a) En palabras simples (intuición): Entrar a una habitación con una linterna, registrar lo que hay en ella, y al salir apagar la linterna y cerrar la puerta para no confundir a los que entren a la habitación vecina.
• (b) Definición técnica paso a paso: Restauración del estado de la tabla hash al retornar de la recursión. Al descender por la rama izquierda, registramos la suma del nodo actual en el mapa; al regresar al padre, decrementamos inmediatamente ese contador en 1. Esto garantiza que las sumas acumuladas en el subárbol izquierdo no existan en el mapa cuando el algoritmo explore el subárbol derecho.
• (c) Cómo funciona en Rust (memoria y tipos): Muta la misma instancia de &mut HashMap<i64, usize> en el Heap sin clonar el mapa en cada llamada, manteniendo el consumo espacial en O(H) estricto.
• (d) Error típico de Junior: Clonar el HashMap en cada llamada recursiva (map.clone()), lo cual gasta O(N) memoria y tiempo en cada nodo, arruinando la complejidad temporal a O(N²).

Caso Base del Prefijo Cero (prefix_counts[0] = 1)#

• (a) En palabras simples (intuición): El punto de partida de un velocímetro antes de arrancar el auto siempre es 0 km. Si el primer viaje mide 8 km, la resta 8 - 0 = 8 solo funciona si el cero existe como referencia inicial.
• (b) Definición técnica paso a paso: Inicialización obligatoria del mapa de prefijos con { 0: 1 }. Representa un "camino vacío" virtual antes de la raíz. Permite detectar de forma natural caminos válidos cuya suma objetivo comienza exactamente en el nodo raíz (S_{actual} - target = 0).
• (c) Cómo funciona en Rust (memoria y tipos): Se inserta con prefix_counts.insert(0, 1) antes de disparar la primera llamada recursiva al DFS.
• (d) Error típico de Junior: Omitir esta inserción; el algoritmo no detectará jamás ningún camino que nazca directamente desde la raíz.

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

Check Subtree: Por Qué la Serialización Exige Marcadores Nulos#

Consideremos dos árboles binarios con formas completamente diferentes:

Árbol A:        1               Árbol B:        1
                 \                             /
                  2                           2

• Si serializamos en Pre-Order sin marcadores nulos:
• Árbol A: emite 1, 2
• Árbol B: emite 1, 2

¡Ambas cadenas son idénticas a pesar de que los árboles tienen estructuras opuestas!

• Ahora, agreguemos marcadores nulos # y delimitadores ,:
• Árbol A (hijo izq nulo, der 2): ,1,#,2,#,#,
• Árbol B (hijo izq 2, der nulo): ,1,2,#,#,#,

¡Las cadenas son radicalmente distintas y reflejan la topología física exacta en RAM! Por tanto, si la cadena serializada de T₂ es una subcadena de la cadena de T₁, entonces T₂ es con certeza matemática un subárbol idéntico de T₁.

Paths with Sum: La Matemática del Prefix Sum en Grafos Dirigidos#

En un arreglo unidimensional, el problema de sub-arreglos que suman K (LeetCode 560) se resuelve en O(N) usando un mapa de frecuencias de sumas de prefijo. En un árbol binario, el problema es conceptualmente idéntico porque cualquier camino descendente desde la raíz hasta un nodo D forma una lista lineal única de ancestros:

Sea Sᵢ la suma de todos los valores desde la raíz R hasta el nodo nᵢ:

• Suma en el nodo actual: S_D.
• Queremos encontrar si existe algún ancestro nⱼ en ese camino tal que:

• Expresando la suma del camino como diferencia de prefijos:

Si la tabla hash registra cuántas veces apareció la suma Sⱼ en la rama actual, podemos responder la pregunta en tiempo estrictamente constante O(1).

El Peligro de Contaminación Cruzada y el Rol del Backtracking#

A diferencia de un arreglo lineal, un árbol se bifurca:

                 (10)
                /    \
              (5)    (-3)
             /   \      \
           (3)   (2)    (11)

• Cuando el algoritmo desciende por la rama izquierda, visita el nodo 5 (S = 15) y el nodo 3 (S = 18).
• La tabla hash registra temporalmente: { 0: 1, 10: 1, 15: 1, 18: 1 }.
• Al terminar la rama izquierda, la recursión regresa a la raíz 10 y desciende hacia la derecha hacia -3 (S = 7).
• ¿Qué pasaría si no hiciéramos backtracking?

Si el mapa conservara las entradas de la rama izquierda (15 y 18), el nodo 11 (S = 18) buscaría 18 - 8 = 10. Encontraría el 10 (legítimo), pero si el target fuera 3, buscaría 18 - 3 = 15 y ¡encontraría erróneamente el 15 que pertenecía a su primo hermano en la rama izquierda!

• Un camino en CTCI 4.12 solo puede descender en línea recta de padre a hijo.
• El Backtracking (prefix_counts[current_sum] -= 1) borra la existencia del nodo al subir, garantizando que el mapa solo contenga a los ancestros directos activos en la línea vertical actual.

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

Traza de Paths with Sum y Aislamiento de Ramas#

flowchart TD
    subgraph TREE["Árbol con Bifurcación (Target = 8)"]
        R["(10) Sum=10"] --> L1["(5) Sum=15"]
        R --> R1["(-3) Sum=7"]
        L1 --> L2_1["(3) Sum=18 -> 18-8=10 (Match: [5, 3]!)"]
        L1 --> L2_2["(2) Sum=17"]
        R1 --> R2["(11) Sum=18 -> 18-8=10 (Match: [-3, 11]!)"]
    end
    subgraph MAP["Estado del Prefix Map durante Backtracking"]
        M1["En Rama Izquierda: {0:1, 10:1, 15:1, 18:1}"] --> RET["Retorno a Raíz: Borra 18 y 15 -> Queda {0:1, 10:1}"]
        RET --> M2["En Rama Derecha: {0:1, 10:1, 7:1, 18:1}"]
    end

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

Ejecución de paths_with_sum_optimal con target = 8:

STACK                                            HEAP
+------------------------------------+          +--------------------------------------+
| Frame dfs(node: 10, sum: 0)        |          | prefix_counts: HashMap<i64, usize>   |
|   current_sum = 0 + 10 = 10        |          |   0 -> 1                             |
|   needed = 10 - 8 = 2 (No en mapa) |          |  10 -> 1                             |
+------------------------------------+          +--------------------------------------+
| Frame dfs(node: 5, sum: 10)        |                             |
|   current_sum = 10 + 5 = 15        |          +------------------+-------------------+
|   needed = 15 - 8 = 7 (No en mapa) |          |  15 -> 1                             |
+------------------------------------+          +--------------------------------------+
| Frame dfs(node: 3, sum: 15)        |                             |
|   current_sum = 15 + 3 = 18        |          +------------------+-------------------+
|   needed = 18 - 8 = 10 (¡EN MAPA!) |--------->|  18 -> 1                             |
|   paths += prefix_counts[10] (1)   |          +--------------------------------------+
+------------------------------------+

Encuentro de camino: ¡El tramo [5, 3] suma 8!
Al salir de Node 3:
- prefix_counts.get_mut(18) se decrementa a 0 -> Se remueve del HashMap.
- El marco de Node 3 se destruye del Stack de la CPU.

Al salir de Node 5:
- prefix_counts.get_mut(15) se decrementa a 0 -> Se remueve del HashMap.
- El mapa vuelve a contener únicamente: { 0: 1, 10: 1 }.

Llamada a la rama derecha dfs(node: -3, sum: 10):
- current_sum = 10 + (-3) = 7.
- needed = 7 - 8 = -1 (No en mapa).
- El mapa registra 7: { 0: 1, 10: 1, 7: 1 }.
¡CERO contaminación de los números 15 y 18 de la rama izquierda!

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

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

//! Día 27: Check Subtree (CTCI 4.10, LeetCode 572) y Paths with Sum (CTCI 4.12, LeetCode 437) en Rust.
//! Compilable y verificable con `rustc --test`.

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

pub fn is_same_tree(p: &Option<Box<TreeNode>>, q: &Option<Box<TreeNode>>) -> bool {
    match (p, q) {
        (None, None) => true,
        (Some(n1), Some(n2)) => {
            n1.val == n2.val && is_same_tree(&n1.left, &n2.left) && is_same_tree(&n1.right, &n2.right)
        }
        _ => false,
    }
}

/// CTCI 4.10 / LeetCode 572: Check Subtree.
pub fn check_subtree(t1: &Option<Box<TreeNode>>, t2: &Option<Box<TreeNode>>) -> bool {
    if t2.is_none() { return true; }
    if t1.is_none() { return false; }

    if is_same_tree(t1, t2) { return true; }

    let n1 = t1.as_ref().unwrap();
    check_subtree(&n1.left, t2) || check_subtree(&n1.right, t2)
}

/// Serialización canónica con marcadores nulos.
pub fn serialize_preorder(root: &Option<Box<TreeNode>>) -> String {
    let mut s = String::new();
    fn helper(node: &Option<Box<TreeNode>>, out: &mut String) {
        match node {
            None => out.push_str(",#"),
            Some(n) => {
                out.push(',');
                out.push_str(&n.val.to_string());
                helper(&n.left, out);
                helper(&n.right, out);
            }
        }
    }
    helper(root, &mut s);
    s.push(',');
    s
}

/// CTCI 4.12 / LeetCode 437: Paths with Sum en O(N) con Prefix Sum y Backtracking.
pub fn paths_with_sum_optimal(root: &Option<Box<TreeNode>>, target_sum: i64) -> usize {
    let mut prefix_counts: HashMap<i64, usize> = HashMap::new();
    prefix_counts.insert(0, 1);

    fn dfs(
        node: &Option<Box<TreeNode>>,
        running_sum: i64,
        target: i64,
        prefix_counts: &mut HashMap<i64, usize>,
    ) -> usize {
        let n = match node {
            Some(node) => node,
            None => return 0,
        };

        let current_sum = running_sum + (n.val as i64);
        let needed = current_sum - target;

        let mut total_paths = prefix_counts.get(&needed).copied().unwrap_or(0);

        *prefix_counts.entry(current_sum).or_insert(0) += 1;

        total_paths += dfs(&n.left, current_sum, target, prefix_counts);
        total_paths += dfs(&n.right, current_sum, target, prefix_counts);

        // Backtracking
        if let Some(count) = prefix_counts.get_mut(&current_sum) {
            *count -= 1;
            if *count == 0 {
                prefix_counts.remove(&current_sum);
            }
        }

        total_paths
    }

    dfs(root, 0, target_sum, &mut prefix_counts)
}

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

    #[test]
    fn test_check_subtree() {
        let mut t1 = TreeNode::new(3);
        let mut n4 = TreeNode::new(4);
        n4.left = Some(Box::new(TreeNode::new(1)));
        n4.right = Some(Box::new(TreeNode::new(2)));
        t1.left = Some(Box::new(n4));
        t1.right = Some(Box::new(TreeNode::new(5)));
        let tree1 = Some(Box::new(t1));

        let mut t2 = TreeNode::new(4);
        t2.left = Some(Box::new(TreeNode::new(1)));
        t2.right = Some(Box::new(TreeNode::new(2)));
        let tree2 = Some(Box::new(t2));

        assert!(check_subtree(&tree1, &tree2));
    }

    #[test]
    fn test_paths_with_sum() {
        let mut root = TreeNode::new(10);
        let mut n5 = TreeNode::new(5);
        let mut n3 = TreeNode::new(3);
        n3.left = Some(Box::new(TreeNode::new(3)));
        n3.right = Some(Box::new(TreeNode::new(-2)));
        let mut n2 = TreeNode::new(2);
        n2.right = Some(Box::new(TreeNode::new(1)));
        n5.left = Some(Box::new(n3));
        n5.right = Some(Box::new(n2));
        let mut n_neg3 = TreeNode::new(-3);
        n_neg3.right = Some(Box::new(TreeNode::new(11)));
        root.left = Some(Box::new(n5));
        root.right = Some(Box::new(n_neg3));
        let tree = Some(Box::new(root));

        assert_eq!(paths_with_sum_optimal(&tree, 8), 3);
    }
}

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

from collections import defaultdict
from typing import Dict, Optional
from practica.dia_23_binary_tree_bst_traversals import TreeNode

def check_subtree(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
    """CTCI 4.10 / LeetCode 572: Check Subtree en O(N + k * M)."""
    if t2 is None: return True
    if t1 is None: return False

    def _is_same(n1: Optional[TreeNode], n2: Optional[TreeNode]) -> bool:
        if not n1 and not n2: return True
        if not n1 or not n2: return False
        return n1.val == n2.val and _is_same(n1.left, n2.left) and _is_same(n1.right, n2.right)

    if _is_same(t1, t2): return True
    return check_subtree(t1.left, t2) or check_subtree(t1.right, t2)

def paths_with_sum_optimal(root: Optional[TreeNode], target_sum: int) -> int:
    """CTCI 4.12 / LeetCode 437: Prefix Sum HashMap + Backtracking en O(N)."""
    prefix_counts: Dict[int, int] = defaultdict(int)
    prefix_counts[0] = 1

    def _dfs(node: Optional[TreeNode], current_sum: int) -> int:
        if not node: return 0

        current_sum += node.val
        total = prefix_counts[current_sum - target_sum]

        prefix_counts[current_sum] += 1
        total += _dfs(node.left, current_sum)
        total += _dfs(node.right, current_sum)

        # Backtracking
        prefix_counts[current_sum] -= 1
        return total

    return _dfs(root, 0)

5. Las 3 Trampas Clásicas en Entrevistas#

1. Serializar sin Marcadores Nulos en Check Subtree: - Si serializas simplemente con valores numéricos 1, 2, un árbol con raíz 1 y solo hijo derecho 2 generará la misma cadena que una raíz 1 con solo hijo izquierdo 2. Es mandatorio serializar # para cada puntero nulo y separar con delimitadores ,.
2. Olvidar el Caso Base prefix_counts[0] = 1: - Si un camino válido inicia exactamente en la raíz (ejemplo: la raíz vale 8 y target_sum = 8), la resta es 8 - 8 = 0. Si no inicializas el prefijo cero con 1, jamás se contarán los caminos que nacen en la raíz.
3. Olvidar el Paso de Backtracking en el HashMap: - Un árbol se bifurca. Si la rama izquierda acumuló una suma de 15 y no la descuentas al regresar al padre, cuando el algoritmo explore la rama derecha creerá que puede formar un camino usando un nodo de la rama hermana, lo cual viola la causalidad descendente padre-hijo.

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

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

1. LeetCode 572 — Subtree of Another Tree (Easy): - Identidad de subárbol estructural idéntica a CTCI 4.10.
2. LeetCode 437 — Path Sum III (Medium): - Conteo de caminos con suma objetivo mediante Prefix Sum HashMap y Backtracking (CTCI 4.12).
3. LeetCode 100 — Same Tree (Easy): - Función auxiliar base is_same_tree.

8. Tarea en Papel para Hoy#

Toma una hoja de papel y realiza a mano la traza de paths_with_sum_optimal con target_sum = 5 en el árbol: Raíz = 3, Izq = 2, Der = 1, Izq de 2 = 3, Der de 1 = 4.

1. Dibuja el árbol y anota la suma acumulada running_sum en cada nodo.
2. Muestra el estado del mapa prefix_counts al bajar por la rama izquierda (3 -> 2 -> 3).
3. Muestra cómo el backtracking limpia el mapa al regresar a la raíz.
4. Muestra el cálculo en la rama derecha (3 -> 1 -> 4) y verifica que los caminos encontrados suman exactamente 5.

Navegación:

• ← Volver a Sesión 26: CTCI Ch4 — Topological Sort y Build Order
• Avanzar a Sesión 28: Grokking Ch7 — Dijkstra y Consolidación Semana 4 →