Entrevista técnica de código: Encontrar el ancestro común más bajo (LCA) de un árbol binario

Problema y alcance

Dado un árbol binario arbitrario y dos nodos distintos p y q en él, devuelve su ancestro común más bajo (LCA). Un nodo es ancestro de sí mismo. El LCA es el nodo más profundo cuyo subárbol contiene a ambos objetivos, por lo que si p es un ancestro de q, la respuesta es el propio p.

Cuatro detalles definen el contrato base: el árbol no es un árbol binario de búsqueda; las entradas identifican objetos de nodo en lugar de valores; nodos separados pueden tener el mismo valor; y se garantiza que tanto p como q están en el árbol. Comparar valores viola silenciosamente ese contrato. Reutilizar la recursión base tras eliminar la garantía de existencia también produce un falso positivo sutil.

a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

Aquí, LCA(d, h) = b, LCA(b, h) = b y LCA(e, f) = a. Esta pregunta está dirigida a ingenieros de software de quienes se espera que comprendan el recorrido de árboles, la semántica recursiva y la complejidad. El caso base solicita una sola consulta. La profundidad no acotada, los objetivos ausentes, los punteros al padre o muchas consultas sobre un mismo árbol estático son restricciones de seguimiento que cambian la mejor solución.

Qué evalúa el entrevistador

La primera observación útil transforma "más bajo" en estructura: la respuesta es el último nodo común en los caminos de la raíz a p y de la raíz a q. Almacenar ambos caminos es correcto, pero innecesario. Una deducción más precisa pide a cada subárbol que reporte uno de tres estados: ningún objetivo encontrado, un objetivo encontrado o el punto donde ambos objetivos ya se han cruzado.

Una respuesta sólida define con precisión el valor de retorno recursivo. Para un subárbol con raíz en node, la función devuelve:

• null cuando el subárbol no contiene ni a p ni a q;
• p o q cuando un objetivo descubierto debe propagarse hacia arriba;
• otro nodo cuando ese nodo ya es el LCA dentro de este subárbol.

Cuando ambos resultados recursivos son no nulos, los objetivos se cruzan a través de diferentes lados del nodo actual, por lo que el nodo actual es la respuesta. Cuando solo un lado es no nulo, su resultado se propaga. El caso base retorna inmediatamente cuando el nodo actual es un objetivo porque la existencia está garantizada: si el otro objetivo está debajo de él, este nodo es el LCA; de lo contrario, este nodo debe reportar un objetivo a un ancestro.

La trampa del contrato es importante. Si q está ausente, el algoritmo base puede devolver p; no prueba además que ambos objetivos existan. Una vez que se elimina la garantía, el resultado recursivo necesita un conteo de coincidencias. Para un árbol con n nodos y altura h, una consulta visita cada nodo en el peor de los casos, por lo que el tiempo es O(n) y la pila recursiva es O(h). En un árbol desbalanceado (skewed), h = n, y la pila de llamadas puede convertirse en el punto de falla en lugar del trabajo algorítmico.

Preguntas para aclarar primero

• ¿Las entradas son referencias a nodos o valores? Las referencias permiten valores duplicados, por lo que se debe comparar con node === p. La búsqueda por valor solo es válida cuando la unicidad es parte del contrato.
• ¿Se garantiza que ambos objetivos existen y son distintos? La recursión base se basa en la existencia. Si alguno puede estar ausente, devuelve también un conteo de coincidencias. Si se permite p === q, define si encontrar ese objeto una vez es suficiente.
• ¿Es este un árbol binario arbitrario o un árbol binario de búsqueda? Un árbol arbitrario necesita una búsqueda estructural. Un BST puede seguir el orden de claves por un solo camino, pero las claves duplicadas y la identidad por referencia pueden invalidar ese atajo.
• ¿Cuáles son la cantidad máxima de nodos y la altura máxima? Un árbol balanceado tiene una profundidad de recursión de O(log n). Una cadena de 100,000 nodos requiere una pila explícita y un mapa de padres para evitar el desbordamiento de la pila en tiempo de ejecución.
• ¿Cuántas consultas se dirigen al mismo árbol estático? Una sola consulta favorece DFS directo. Muchas consultas pueden justificar el precálculo de la profundidad y de los ancestros 2^k para consultas en O(log n).
• ¿Los nodos ya tienen punteros al padre? Entonces no es necesario recorrer desde la raíz. Alinea las profundidades y sube conjuntamente, o registra una cadena de ancestros y encuentra su primera intersección.

Estructura de respuesta en 30 segundos

"Primero confirmaría que se trata de un árbol binario arbitrario y que p y q son referencias a nodos con existencia garantizada, de modo que los valores duplicados no afecten la identidad. Mi función recursiva devuelve el objetivo o el LCA descubierto en un subárbol. Un nodo nulo devuelve null, y un nodo igual a p o q se devuelve a sí mismo. Después de buscar en ambos hijos, dos resultados no nulos significan que los objetivos se cruzan en el nodo actual; de lo contrario, propago el único resultado no nulo. Cada nodo se visita como máximo una vez, lo que da un tiempo en el peor de los casos de O(n) y un espacio de pila de O(h). Probaría ramas separadas, un objetivo que es ancestro del otro, valores duplicados y un árbol desbalanceado. Si los objetivos pueden estar ausentes, agrego un conteo de coincidencias; si la altura no está acotada, uso una pila explícita para construir enlaces a los padres".

Solución paso a paso

Paso 1: Establecer una línea base de caminos correcta

El enfoque más directo encuentra los caminos de la raíz a p y de la raíz a q, los compara desde la raíz y devuelve su último nodo compartido. Explica la definición con claridad y valida naturalmente que ambos objetivos existen. Dos pasadas DFS aún toman un tiempo de O(n), mientras que los caminos y la recursión usan un espacio de O(h). Una implementación que retiene cada nodo explorado puede crecer a un espacio de O(n).

La redundancia radica en que ambas búsquedas recorren un prefijo compartido extenso. La única información necesaria es lo que un subárbol reporta a su padre, por lo que los dos caminos se pueden comprimir en un solo recorrido en postorden.

Paso 2: Definir el valor de retorno y recorrer una sola vez

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

El código compara la identidad del objeto y nunca lee value, por lo que valores iguales en nodos separados son seguros. El postorden es esencial: el nodo actual necesita los reportes de ambos hijos antes de decidir si es el primer punto de encuentro.

Paso 3: Probarlo con un invariante

Considera cualquier subárbol con raíz en node y asume que ambas llamadas recursivas satisfacen la definición del valor de retorno.

1. Si node es nulo, el subárbol no contiene ningún objetivo, por lo que null es correcto.
2. Si node es p o q, devuelve node. Dado que ambos objetivos existen, este objetivo es el LCA porque contiene al otro objetivo, o debe reportar un objetivo a un ancestro.
3. Si ambos resultados de los hijos son no nulos, cada lado reporta un objetivo. Ningún nodo más profundo pertenece a ambos lados, por lo que node es el ancestro común más profundo.
4. Si exactamente un lado es no nulo, el nodo actual no crea un nuevo punto de encuentro. El objetivo de ese lado o el LCA completado es el único resultado válido para propagar. Si ambos son nulos, devuelve null.

Por inducción estructural, el resultado devuelto en la raíz es el LCA del árbol completo. La prueba también cubre el caso del ancestro que suele pasarse por alto: cuando p es un ancestro de q, alcanzar p lo devuelve sin requerir que q se devuelva desde abajo una segunda vez.

Paso 4: Declarar los costos reales de tiempo y espacio

En el peor de los casos, la función visita todos los n nodos y realiza un trabajo constante en cada uno, por lo que el tiempo es O(n). Encontrar un objetivo temprano puede omitir parte del árbol, pero el mejor de los casos no determina la cota del peor de los casos.

El espacio auxiliar es de O(h) para la recursión. En un árbol balanceado, h = O(log n); en un árbol completamente desbalanceado, h = n. La referencia del nodo devuelto no cuenta como almacenamiento auxiliar. Calificar la solución como de espacio O(1) ignora la pila de llamadas.

Paso 5: Cambiar el contrato cuando los objetivos pueden estar ausentes

Sin la garantía de existencia, la función base puede fallar: si solo p se encuentra en el árbol, propaga p hasta la raíz. Una versión segura distingue un nodo candidato de la cantidad de objetivos realmente encontrados.

interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

Esta versión todavía asume p !== q. Si se puede suministrar la misma referencia dos veces, define el contrato primero: encontrar ese nodo una vez debería devolverlo en lugar de continuar requiriendo matches === 2. Los cambios en las restricciones deben preceder a los cambios de código.

Paso 6: Usar una pila explícita y un mapa de padres para árboles profundos

Cuando la altura puede acercarse a 100,000, el espacio asintótico de recursión no cambia, pero la pila de llamadas del entorno de ejecución puede desbordarse primero. Recorre con una pila explícita y registra parent.get(child) = node hasta que tanto p como q estén en el mapa. Coloca a cada ancestro de p en un conjunto, luego sube desde q; el primer miembro encontrado en el conjunto es el LCA.

Esta alternativa sigue tomando un tiempo de O(n) y usa un espacio explícito de O(n). Puede usar más memoria en el heap que la recursión, pero traslada el recurso desde una pila de llamadas pequeña hacia estructuras de datos controladas. Para una sola consulta en un árbol con una cota de altura razonable, la versión recursiva es más corta y más fácil de demostrar, por lo que el mapa de padres no debería ser el valor predeterminado automático.

Paso 7: Validar la semántica con casos adversos

Como mínimo, cubre esta matriz:

Más allá de los ejemplos fijos, genera árboles pequeños aleatorios y compara el resultado de una pasada con la línea base de caminos por identidad de objeto. Dado que la línea base y el método optimizado usan enfoques diferentes, esta comprobación diferencial detecta más defectos que unas pocas aserciones manuales aisladas.

Respuesta de muestra de alta calidad

"Primero fijaría el contrato: este es un árbol binario arbitrario, p y q son referencias a nodos distintos con existencia garantizada, y los valores pueden repetirse. Por lo tanto, mi código compara referencias, no valores.

Uso un DFS en postorden de una sola pasada. Para un subárbol, la función devuelve null, un objetivo descubierto o un LCA ya encontrado. Un nodo nulo devuelve null, y un nodo actual igual a cualquiera de los objetivos se devuelve a sí mismo. Después de aplicar la recursión en ambos hijos, dos resultados no nulos significan que los objetivos se cruzan por primera vez en el nodo actual, por lo que lo devuelvo. Con solo un lado no nulo, propago ese resultado.

La corrección se deduce de ese invariante de retorno. Cuando los objetivos están en subárboles hijos diferentes, ningún nodo más profundo puede contener a ambos. Cuando un objetivo es ancestro del otro, devolver el objetivo ancestro inmediatamente coincide con la definición. El peor de los casos visita cada nodo una vez con un tiempo de O(n) y un espacio de pila recursiva de O(h); un árbol desbalanceado hace que la profundidad de la pila sea O(n).

Probaría ramas opuestas, un objetivo ancestro, un subárbol profundo y valores duplicados. Si no se garantiza la existencia de los objetivos, esta función podría devolver el único objetivo presente, por lo que también devolvería un conteo de coincidencias y aceptaría un candidato solo después de encontrar ambos. Si el árbol puede ser muy profundo, usaría una pila explícita y un mapa de padres para evitar el desbordamiento de la pila de llamadas".

Errores comunes

• Tratar el árbol como un BST y elegir lados por valor → los árboles binarios arbitrarios no tienen orden de claves, y los valores duplicados no identifican nodos → busca por estructura y compara referencias de nodos.
• Devolver el nodo actual cuando cualquiera de los hijos es no nulo → un solo objetivo en un lado es promovido hasta la raíz → devuelve el nodo actual solo cuando ambos lados son no nulos; de lo contrario, propaga el resultado no nulo.
• Asumir que p debe estar estrictamente debajo de la respuesta → un nodo es ancestro de sí mismo, por lo que p puede ser la respuesta → haz que la identidad del nodo actual sea un caso base.
• Reutilizar el algoritmo base cuando los objetivos pueden estar ausentes → encontrar un objetivo todavía produce un resultado no nulo → devuelve un conteo de coincidencias y ten éxito solo después de encontrar ambos.
• Afirmar un espacio auxiliar de O(1) → los marcos recursivos crecen con la altura del árbol y alcanzan O(n) en una cadena → reporta O(h) y usa una pila explícita cuando la profundidad no está acotada.
• Precalcular binary lifting para una sola consulta → el código y el almacenamiento de O(n log n) no se amortizan → usa un solo DFS para una consulta y preprocesa solo para muchas consultas.
• Probar solo dos hojas en lados opuestos → los errores relacionados con ancestros, valores duplicados, objetivos ausentes y profundidad quedan ocultos → organiza las pruebas alrededor de los límites del contrato.

Preguntas de seguimiento

¿Qué pasa si p o q podrían no estar en el árbol?

Devuelve tanto un nodo candidato como un conteo de coincidencias desde la recursión. Con objetivos distintos, el conteo es 0, 1 o 2. Devuelve el LCA candidato solo cuando el resultado en la raíz tenga un conteo de 2; de lo contrario, devuelve null. Ejecutar el algoritmo base y simplemente verificar un resultado no nulo es insuficiente porque el único objetivo presente es en sí mismo no nulo.

¿Qué pasa si el árbol tiene 100,000 nodos y puede estar completamente desbalanceado?

Usa una pila explícita para construir un mapa de padres. Una vez encontrados ambos objetivos, almacena los ancestros de p en un conjunto y sigue la cadena de padres de q hasta la primera intersección. Toma un tiempo de O(n) y un espacio en heap de O(n), pero no consume 100,000 marcos de llamada del lenguaje. Si el espacio en heap también está restringido, aclara si se dispone de punteros al padre o de una interfaz de recorrido controlada en lugar de asumir que la recursión es segura.

¿Qué pasa si el mismo árbol estático debe responder un millón de consultas de LCA?

Un DFS de O(n) por consulta ya no es viable. Precalcula la profundidad de cada nodo y sus ancestros de 2^k en un tiempo y espacio de O(n log n). Para cada consulta, eleva el nodo más profundo a la misma profundidad, luego eleva ambos desde el mayor k hacia abajo, lo que toma O(log n) por consulta. Con volúmenes de consulta aún mayores, puede valer la pena evaluar un recorrido de Euler más RMQ; la frecuencia de actualización, la memoria y los requisitos de latencia deciden qué esquema de preprocesamiento es el adecuado.

¿Qué pasa si cada nodo ya tiene un puntero al padre?

No es necesario recorrer desde la raíz. Calcula ambas profundidades, eleva el nodo más profundo hasta que las profundidades coincidan y luego sube ambos hasta que sean iguales. Esto toma un tiempo de O(h) y un espacio adicional de O(1). Alternativamente, almacena todos los ancestros de p y sube desde q; es más simple pero usa un conjunto de O(h).

¿Cómo cambia la solución para un árbol binario de búsqueda?

Con claves únicas y un contrato que localiza objetivos por clave, ve hacia la izquierda cuando ambas claves objetivo sean menores, hacia la derecha cuando ambas sean mayores y, de lo contrario, devuelve el punto de división actual o el objetivo. Esto toma un tiempo de O(h) y un espacio iterativo de O(1). Si los valores pueden repetirse o las entradas aún identifican objetivos por referencia, define primero la ubicación de claves duplicadas y la semántica de búsqueda; dos valores por sí solos no pueden reemplazar con seguridad el algoritmo para árboles arbitrarios.