Sesión 25: CTCI Capítulo 4 — Successor (4.6) y Lowest Common Ancestor (4.8)#

Navegación rápida:

• ← Sesión 24: CTCI Ch4 — Validate BST y Check Balanced
• Sesión 26: CTCI Ch4 — Topological Sort y Build Order →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_25.rs

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

En esta sesión abordamos las dos preguntas de navegación genealógica más sofisticadas de CTCI: cómo avanzar al siguiente elemento en el orden secuencial de un árbol y cómo encontrar el ancestro común más profundo entre dos nodos. Consulta el Glosario Maestro y la Guía de Diagramas.

Sucesor In-Order (In-Order Successor)#

• (a) En palabras simples (intuición): En una fila ordenada de estudiantes por estaturas, es el compañero que está inmediatamente detrás de ti (el siguiente más alto).
• (b) Definición técnica paso a paso: Dado un nodo N en un Binary Search Tree, su sucesor in-order es el nodo con el valor estrictamente menor entre todos los nodos que son estrictamente mayores que N.val (el nodo que se visitaría inmediatamente después de N en un recorrido In-Order).
• (c) Cómo funciona en Rust (memoria y tipos): Si el árbol cuenta con enlaces bidireccionales, se navega mediante un Arena (Vec<ArenaNode>). Si no tiene punteros al padre, se localiza mediante búsqueda binaria desde la raíz en O(H) tiempo y O(1) espacio.
• (d) Error típico de Junior: Realizar un recorrido In-Order completo guardando todos los elementos en un vector (O(N) tiempo y memoria) solo para buscar el elemento adyacente.

Arena de Nodos para Enlaces Bidireccionales en Rust (Vec<ArenaNode>)#

• (a) En palabras simples (intuición): Una libreta numerada de páginas fijas. En lugar de que cada página intente agarrar físicamente a la página anterior (lo que rompería el libro), cada página simplemente anota: "mi padre está en la página 3, mi hijo izquierdo en la página 7".
• (b) Definición técnica paso a paso: Patrón de diseño de bajo nivel para Rust seguro (Safe Rust) que resuelve el problema de los ciclos de pertenencia. Un nodo con puntero al padre tiene referencias bidireccionales (P rightarrow C). Como Box exige pertenencia exclusiva y no admite referencias cíclicas, todos los nodos se almacenan en un único vector Vec<ArenaNode> y las relaciones se modelan como índices enteros Option<usize>.
• (c) Cómo funciona en Rust (memoria y tipos): Cero llamadas a unsafe, cero sobrecarga de conteo de referencias (Rc<RefCell<T>>), y máxima localidad de caché al residir todos los nodos en un bloque contiguo del Heap.
• (d) Error típico de Junior: Intentar escribir struct Node { parent: Option<&'a Node> } y luchar durante horas contra el Borrow Checker por conflictos de mutabilidad y tiempos de vida.

Lowest Common Ancestor (LCA / Primer Ancestro Común)#

• (a) En palabras simples (intuición): En un árbol genealógico, el abuelo común más reciente entre dos primos hermanos. No es el tatarabuelo distante ni un tío, sino el punto exacto donde sus dos ramas familiares se separaron.
• (b) Definición técnica paso a paso: Dados dos nodos p y q en un árbol con raíz R, el LCA es el nodo A más profundo tal que tanto p como q son descendientes de A (un nodo puede ser descendiente de sí mismo si p es padre directo de q).
• (c) Cómo funciona en Rust (memoria y tipos): En un árbol binario general sin punteros al padre, se resuelve mediante un recorrido DFS Post-Order que detecta el punto de bifurcación donde una rama encuentra a p y la otra a q.
• (d) Error típico de Junior: Asumir que el LCA siempre es un tercer nodo distinto, olvidando que si p es padre de q, el LCA es el propio p.

LCA en BST por Propiedad de Búsqueda Binaria#

• (a) En palabras simples (intuición): Dividir una bifurcación de caminos. Si dos autos deben viajar a destinos con números 2 y 8, y la autopista actual está en el kilómetro 6, el kilómetro 6 es la última salida compartida donde ambos autos deben separarse a izquierda y derecha.
• (b) Definición técnica paso a paso: Algoritmo optimizado para BSTs (LeetCode 235). Si ambos valores p y q son menores que el nodo actual, el LCA reside obligatoriamente en el subárbol izquierdo. Si ambos son mayores, reside en el subárbol derecho. El primer nodo cuyo valor quede comprendido en el intervalo [min(p, q), max(p, q)] es con certeza absoluta el LCA.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con un bucle while let Some(node) = curr iterativo sin recursión, operando en O(H) tiempo y O(1) memoria auxiliar.
• (d) Error típico de Junior: Usar el algoritmo general de árboles no ordenados (O(N)) en un BST, desperdiciando la propiedad de ordenación logarítmica.

Nivelación de Profundidades en O(1) Espacio#

• (a) En palabras simples (intuición): Dos montañistas escalando a distintas alturas de una montaña que quieren encontrarse en la cima. El que está más abajo debe subir primero hasta colocarse a la misma altura horizontal que el otro; luego ambos caminan hacia arriba al mismo paso hasta cruzarse en el sendero común.
• (b) Definición técnica paso a paso: Técnica utilizada para hallar el LCA cuando los nodos disponen de punteros a sus padres. Se calcula la profundidad de p y q. Se asciende el nodo más profundo Δ = |d_p - d_q| pasos hasta igualar alturas. Luego se ascienden ambos al unísono hasta que coincidan en la misma dirección de memoria.
• (c) Cómo funciona en Rust (memoria y tipos): Idéntico al problema de intersección de listas enlazadas (CTCI 2.7), operando en O(H) tiempo y O(1) memoria.
• (d) Error típico de Junior: Almacenar todos los ancestros de p en un HashSet gastando O(H) memoria extra innecesaria.

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

La Mecánica del Sucesor In-Order (Los Dos Escenarios Físicos)#

Sea un nodo objetivo X en un árbol de búsqueda binaria:

            (20)
           /    \
         (10)   (30)
        /   \
      (5)   (15)
            /
          (12)

Escenario 1: El nodo X TIENE subárbol derecho (X.right ≠ None)#

• Ejemplo: Buscar el sucesor de 10.
• Todo lo que esté a la derecha de 10 es mayor que 10.
• Pero buscamos el menor de los mayores.
• Por tanto, debemos encontrar el valor mínimo dentro del subárbol derecho: el nodo que esté ubicado más a la izquierda posible a partir de X.right.
• Camino: Desde 10, bajamos a la derecha a 15, y luego doblamos a la izquierda a 12.
• 12 no tiene hijo izquierdo ⟹ 12 es el sucesor de 10.

Escenario 2: El nodo X NO TIENE subárbol derecho (X.right == None)#

• Ejemplo: Buscar el sucesor de 15.
• 15 no tiene hijo derecho. Ya procesamos todo su subárbol.
• Debemos ascender por la cadena de padres:
• Mientras seamos el hijo derecho de nuestro padre, significa que ese padre ya fue procesado antes que nosotros en In-Order. Debemos seguir subiendo.
• Nos detenemos en el instante exacto en que seamos el hijo izquierdo de un padre: ese padre aún no ha sido procesado y es obligatoriamente el siguiente en la secuencia.
• Camino:
• Desde 15, subimos a su padre 10. ¿Es 15 el hijo izquierdo de 10? No, es el hijo derecho. Seguimos subiendo.
• Desde 10, subimos a su padre 20. ¿Es 10 el hijo izquierdo de 20? ¡SÍ!
• Nos detenemos: 20 es el sucesor de 15.
• Caso extremo: Si subimos hasta la raíz y nunca fuimos el hijo izquierdo de nadie (ejemplo: nodo 30), el nodo era el máximo global del árbol y retornamos None.

Por Qué Rust Exige un Arena para Punteros al Padre#

En C++ o Java es trivial escribir:

class Node {
    Node* left;
    Node* right;
    Node* parent;
};

¿Por qué en Rust esto no compila con Box?

• Si el padre tiene left: Box<Node>, el padre es el dueño exclusivo del hijo en memoria.
• Si el hijo tiene parent: Box<Node>, ¡el hijo intentaría ser simultáneamente el dueño de su propio padre!
• Esto crea un ciclo de propiedad mutua no resolvible: el compilador no sabe quién debe liberar a quién.
• La alternativa con punteros inteligentes compartidos (Rc<RefCell<Node>>) agrega una enorme sobrecarga de memoria (16 bytes extra por nodo para contadores atómicos y comprobación dinámica de préstamos).
• La solución canónica de Rust: El Arena de Nodos (Vec<ArenaNode>). Todos los nodos residen en un vector central indexado. Un "puntero" es simplemente un Option<usize>. Cero referencias cíclicas, cero panics de RefCell, y máxima seguridad de memoria estática.

La Lógica de Bifurcación de Lowest Common Ancestor (LeetCode 236)#

En un árbol binario general sin punteros ascendentes: Invocamos recursivamente lca(node, p, q):

1. Caso Base: Si node == None o node == p o node == q, retornamos node.
2. Llamadas Recursivas: - left = lca(node.left, p, q) - right = lca(node.right, p, q)
3. Arbitraje de Resultados: - Si left != None y right != None: un objetivo fue encontrado en la rama izquierda y el otro en la derecha. node es el punto exacto de encuentro (el LCA). - Si solo left != None: ambos nodos residen en el subárbol izquierdo (o uno es ancestro del otro). Propagamos left hacia arriba. - Si solo right != None: propagamos right. - Si ambos son None: ninguno de los objetivos existe en este subárbol. Retornamos None.

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

Trayectorias de Sucesor In-Order y Punto de Bifurcación LCA#

flowchart TD
    subgraph SUC["Sucesor In-Order"]
        N20["(20) Raíz"] --- N10["(10)"]
        N20 --- N30["(30)"]
        N10 --- N5["(5)"]
        N10 --- N15["(15)"]
        N15 --- N12["(12)"]
        N10 -.->|"Hijo Der + Todo a la Izq"| N12
        N15 -.->|"Sube a 10 y luego a 20 (Hijo Izq)"| N20
    end
    subgraph LCA["Lowest Common Ancestor de 5 y 12"]
        L20["(20)"] --> L10["(10) ¡Bifurcación LCA!"]
        L10 --> L5["(5) Hallado p"]
        L10 --> L15["(15)"]
        L15 --> L12["(12) Hallado q"]
    end

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

Representación del árbol con Arena (ArenaTree) en memoria contigua:

STACK                                            HEAP (Vector Contiguo de Nodos)
+-------------------------------+               +-----+------+--------+------+-------+
| ArenaTree                     |               | Idx | Val  | Parent | Left | Right |
|   nodes: Vec<ArenaNode> ------+-------------->+-----+------+--------+------+-------+
+-------------------------------+               |  0  |  20  |  None  | Some(1)|Some(2)|
                                                |  1  |  10  | Some(0)| Some(3)|Some(4)|
                                                |  2  |  30  | Some(0)| None | None  |
                                                |  3  |   5  | Some(1)| None | None  |
                                                |  4  |  15  | Some(1)| Some(5)|None |
                                                |  5  |  12  | Some(4)| None | None  |
                                                +-----+------+--------+------+-------+

Traza de inorder_successor_arena(4) (Nodo 15, Val 15):
Paso 1: nodes[4].right es None (Escenario B).
Paso 2: curr = 4, parent_opt = nodes[4].parent = Some(1) (Nodo 10).
        ¿nodes[1].left == Some(4)?
        nodes[1].left es Some(3) != Some(4) (15 es el hijo derecho de 10).
        -> No es hijo izquierdo. Subimos: curr = 1.
Paso 3: parent_opt = nodes[1].parent = Some(0) (Nodo 20).
        ¿nodes[0].left == Some(1)?
        nodes[0].left es Some(1) == Some(1). ¡COINCIDENCIA!
        -> 10 es el hijo izquierdo de 20.
Retorna Some(0) (Nodo con valor 20).
Cero punteros crudos. Cero llamadas a malloc. Acceso a arrays contiguos en RAM en O(H).

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

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

//! Día 25: Successor (CTCI 4.6, LeetCode 285) y Lowest Common Ancestor (CTCI 4.8, LeetCode 235, 236) 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 }
    }
}

/// LeetCode 285: Sucesor In-Order en BST sin puntero al padre en O(H) tiempo y O(1) espacio.
pub fn inorder_successor_bst(root: &Option<Box<TreeNode>>, p_val: i32) -> Option<i32> {
    let mut curr = root.as_ref();
    let mut successor = None;

    while let Some(node) = curr {
        if p_val < node.val {
            successor = Some(node.val);
            curr = node.left.as_ref();
        } else {
            curr = node.right.as_ref();
        }
    }
    successor
}

/// LeetCode 236: Lowest Common Ancestor en Árbol Binario General en O(N).
pub fn lowest_common_ancestor_bt(root: &Option<Box<TreeNode>>, p: i32, q: i32) -> Option<i32> {
    fn helper(node: &Option<Box<TreeNode>>, p: i32, q: i32) -> Option<i32> {
        let n = node.as_ref()?;
        if n.val == p || n.val == q { return Some(n.val); }

        let left = helper(&n.left, p, q);
        let right = helper(&n.right, p, q);

        match (left, right) {
            (Some(_), Some(_)) => Some(n.val),
            (Some(v), None) => Some(v),
            (None, Some(v)) => Some(v),
            (None, None) => None,
        }
    }
    helper(root, p, q)
}

/// LeetCode 235: LCA en un BST en O(H) tiempo y O(1) espacio iterativo.
pub fn lowest_common_ancestor_bst(root: &Option<Box<TreeNode>>, p: i32, q: i32) -> Option<i32> {
    let mut curr = root.as_ref();
    let min_val = p.min(q);
    let max_val = p.max(q);

    while let Some(node) = curr {
        if node.val > max_val {
            curr = node.left.as_ref();
        } else if node.val < min_val {
            curr = node.right.as_ref();
        } else {
            return Some(node.val);
        }
    }
    None
}

// Arena Tree para CTCI 4.6 (Árbol con punteros al padre en Safe Rust)
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ArenaNode {
    pub val: i32,
    pub parent: Option<usize>,
    pub left: Option<usize>,
    pub right: Option<usize>,
}

#[derive(Debug, Default, Clone)]
pub struct ArenaTree {
    pub nodes: Vec<ArenaNode>,
}

impl ArenaTree {
    pub fn new() -> Self { Self::default() }

    pub fn add_node(&mut self, val: i32) -> usize {
        let idx = self.nodes.len();
        self.nodes.push(ArenaNode { val, parent: None, left: None, right: None });
        idx
    }

    pub fn set_left(&mut self, parent: usize, child: usize) {
        self.nodes[parent].left = Some(child);
        self.nodes[child].parent = Some(parent);
    }

    pub fn set_right(&mut self, parent: usize, child: usize) {
        self.nodes[parent].right = Some(child);
        self.nodes[child].parent = Some(parent);
    }

    /// CTCI 4.6: In-Order Successor con puntero al padre.
    pub fn inorder_successor_arena(&self, node_idx: usize) -> Option<usize> {
        if node_idx >= self.nodes.len() { return None; }
        let node = &self.nodes[node_idx];

        if let Some(right_child) = node.right {
            let mut curr = right_child;
            while let Some(left) = self.nodes[curr].left { curr = left; }
            return Some(curr);
        }

        let mut curr = node_idx;
        let mut parent_opt = self.nodes[curr].parent;
        while let Some(parent_idx) = parent_opt {
            if self.nodes[parent_idx].left == Some(curr) {
                return Some(parent_idx);
            }
            curr = parent_idx;
            parent_opt = self.nodes[parent_idx].parent;
        }
        None
    }
}

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

    #[test]
    fn test_successor_and_lca() {
        let mut tree = ArenaTree::new();
        let n20 = tree.add_node(20);
        let n10 = tree.add_node(10);
        let n30 = tree.add_node(30);
        tree.set_left(n20, n10);
        tree.set_right(n20, n30);

        assert_eq!(tree.inorder_successor_arena(n10), Some(n20));
        assert_eq!(tree.inorder_successor_arena(n30), None);
    }
}

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

from typing import Optional
from practica.dia_23_binary_tree_bst_traversals import TreeNode

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

def inorder_successor_with_parent(node: Optional[TreeNodeWithParent]) -> Optional[TreeNodeWithParent]:
    """CTCI 4.6: In-Order Successor con puntero al padre en O(H)."""
    if not node:
        return None

    if node.right:
        curr = node.right
        while curr.left:
            curr = curr.left
        return curr

    curr = node
    parent = node.parent
    while parent and parent.right is curr:
        curr = parent
        parent = parent.parent

    return parent

def lca_binary_tree(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    """CTCI 4.8 / LeetCode 236: LCA en Árbol Binario sin puntero padre en O(N)."""
    if not root or root is p or root is q:
        return root

    left = lca_binary_tree(root.left, p, q)
    right = lca_binary_tree(root.right, p, q)

    if left and right:
        return root
    return left if left else right

5. Las 3 Trampas Clásicas en Entrevistas#

1. Olvidar el Caso donde p es Ancestro Directo de q: - Si p es padre de q, el LCA no es un nodo superior; el LCA es el propio p.
2. Asumir que Ambos Nodos Existen Siempre en el Árbol (Trampa CTCI 4.8): - En LeetCode 236 se garantiza que ambos nodos existen. Pero en CTCI 4.8, si q no pertenece al árbol, el algoritmo básico que retorna root si root is p devolverá p engañosamente. Valida siempre la existencia de ambos nodos antes de declarar un ancestro común legítimo.
3. Desperdiciar O(N) Espacio con un Set Teniendo Punteros al Padre: - Si los nodos tienen puntero parent, guardar todos los ancestros de p en un HashSet consume O(H) memoria extra. La solución senior calcula profundidades y asciende en O(1) espacio auxiliar.

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

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

1. LeetCode 285 — Inorder Successor in BST (Medium): - Sucesor In-Order partiendo desde la raíz en O(H) y espacio O(1).
2. LeetCode 235 — Lowest Common Ancestor of a Binary Search Tree (Medium): - LCA iterativo en BST aprovechando intervalos numéricos.
3. LeetCode 236 — Lowest Common Ancestor of a Binary Tree (Medium): - LCA en árbol binario general con recursión bottom-up.
4. LeetCode 1650 — Lowest Common Ancestor of a Binary Tree III (Medium): - LCA con punteros al padre nivelando profundidades en O(1) espacio.

8. Tarea en Papel para Hoy#

Toma una hoja de papel y dibuja el siguiente árbol: 20 -> [10, 30], 10 -> [5, 15], 15 -> [12, None], 30 -> [None, 40].

1. Aplica a mano las reglas de los dos escenarios para encontrar el Sucesor In-Order de: - Nodo 12 - Nodo 10 - Nodo 15 - Nodo 40
2. Traza manualmente la búsqueda de LCA entre 5 y 12 mostrando el punto exacto de bifurcación.

Navegación:

• ← Volver a Sesión 24: CTCI Ch4 — Validate BST y Check Balanced
• Avanzar a Sesión 26: CTCI Ch4 — Topological Sort y Build Order →