Entrevista técnica de código: serializar y deserializar un árbol binario

Problema y contexto aplicable

Implementa dos funciones para un árbol binario arbitrario:

• serialize(root) convierte el árbol en una cadena.
• deserialize(data) reconstruye un árbol con los mismos valores y forma.

Asume que los valores de los nodos son enteros de 32 bits con signo, que el árbol puede estar vacío y que la cadena serializada solo necesita interoperar con este decodificador. Para la implementación recursiva en la entrevista, asume que la altura del árbol se ajusta al límite de la pila de llamadas (call-stack) del lenguaje. El decodificador que se muestra a continuación también rechaza el texto con formato incorrecto en lugar de aceptar silenciosamente un árbol parcial.

Para este árbol:

1
       / \
      2   3
         / \
        4   5

el formato elegido es:

1,2,#,#,3,4,#,#,5,#,#

Cada entero registra un nodo, # registra un hijo ausente, las comas separan los tokens y el recorrido en preorden determina cómo se consumen los tokens. Material público actualizado en 2026 presenta exactamente este problema con soluciones en preorden y por niveles (level-order), mientras que una grabación de interviewing.io muestra que se planteó en una entrevista de prueba con un ingeniero de Meta. Esto respalda que se trata de un ejercicio de programación representativo y vigente, sin afirmar que todas las empresas o entrevistas lo utilicen.

Qué evalúa el entrevistador

La primera señal es si el candidato define la reversibilidad antes de elegir un recorrido. Los valores en preorden por sí solos son insuficientes. Una raíz 1 con hijo izquierdo 2 y una raíz 1 con hijo derecho 2 producen ambas [1, 2] a menos que se codifiquen los hijos ausentes. Sus formas marcadas difieren:

Left child:  1,2,#,#,#
Right child: 1,#,2,#,#

La segunda señal es diseñar el codificador y el decodificador como funciones inversas. En preorden, un decodificador lee un token. # completa un subárbol vacío. Un valor inicia un nodo, tras el cual el siguiente subárbol completo pertenece al hijo izquierdo y el subsiguiente subárbol completo pertenece al hijo derecho. Por lo tanto, el formato proporciona sus propios límites recursivos sin necesidad de almacenar los tamaños de los subárboles.

La tercera señal es un argumento real de corrección. Para un árbol con n nodos, hay n + 1 punteros a hijos nulos, por lo que la codificación contiene exactamente 2n + 1 tokens. Más importante aún, el decodificador debe consumir exactamente los tokens de un subárbol y dejar el iterador posicionado en el siguiente subárbol. La inducción estructural demuestra esta propiedad.

Por último, el entrevistador busca límites de ingeniería: entrada inválida, valores negativos y duplicados, profundidad de recursión, tamaño de salida y cuándo BFS o un formato de serialización para producción son la mejor opción.

Preguntas de clarificación antes de responder

• ¿Es este un árbol binario arbitrario o un árbol binario de búsqueda (BST)? Un árbol arbitrario necesita marcadores estructurales. A veces, un BST se puede reconstruir a partir del preorden junto con una política explícita de duplicados.
• ¿Debe la cadena seguir un formato de transmisión existente? Esta consigna permite un formato privado. El almacenamiento entre servicios requiere control de versiones del esquema, reglas de compatibilidad y, a menudo, un códec estándar.
• ¿Pueden los valores de los nodos contener el delimitador o el centinela? Son enteros, por lo que la coma y # son inequívocos. Cadenas de texto generales necesitarían caracteres de escape o prefijos de longitud.
• ¿Puede el árbol estar vacío? Sí. Se serializa como #.
• ¿Puede la entrada ser extremadamente profunda o maliciosa? La respuesta recursiva asume una altura acotada. Los árboles no confiables o profundamente desbalanceados requieren una pila explícita y límites de recursos.
• ¿Recibirá deserialize únicamente salidas confiables de serialize? El código se mantiene estricto: se rechazan texto vacío, enteros inválidos, árboles truncados y tokens sobrantes.
• ¿Optimizamos para legibilidad o para el mínimo de bytes? El texto en preorden es fácil de explicar y probar. Un protocolo binario compacto codificaría etiquetas y enteros de forma diferente.

Estructura de respuesta de 30 segundos

«Utilizaré un recorrido en preorden y emitiré # para cada hijo ausente. Un token de valor significa crear un nodo y luego decodificar recursivamente sus subárboles izquierdo y derecho; # significa retornar None. Los marcadores nulos son necesarios porque los valores por sí solos no pueden distinguir un hijo izquierdo de uno derecho. El codificador y el decodificador se reflejan mutuamente, y la inducción estructural muestra que cada llamada de decodificación consume exactamente un subárbol. Ambas operaciones toman tiempo O(n) y producen datos O(n), con una pila de llamadas de O(h) para una altura h. También rechazaré entradas truncadas o con tokens sobrantes y mencionaré una versión iterativa con BFS o basada en pila cuando la profundidad no esté acotada».

Análisis detallado paso a paso

Paso uno: rechazar el enfoque básico de solo valores con un contraejemplo.

Los valores en preorden, inorden o postorden no identifican de forma única un árbol binario arbitrario por sí solos. Incluso combinar preorden e inorden se vuelve ambiguo cuando se permiten valores duplicados. El formato debe codificar tanto la forma como los valores. Un marcador nulo es la señal de forma más simple para un formato de texto en una entrevista.

Paso dos: elegir una gramática que se pueda decodificar de izquierda a derecha.

El formato se puede describir recursivamente:

tree := "#"
      | integer "," tree "," tree

La implementación real tokeniza primero por comas, de modo que cada llamada recursiva consume un token y, para un valor, dos codificaciones de subárboles subsiguientes. El texto de un entero con signo nunca contiene , ni #. Un árbol vacío es #; una hoja con valor 7 es 7,#,#.

Esta gramática también proporciona un invariante de conteo útil. Un árbol binario con n nodos reales tiene n + 1 punteros a hijos nulos. Por lo tanto, la serialización emite n tokens de valor y n + 1 tokens nulos, para un total de 2n + 1 tokens. El conteo es una herramienta de diagnóstico, no un sustituto del análisis sintáctico (parsing): los tokens con formato incorrecto aún pueden sumar un total impar.

Paso tres: implementar las operaciones recursivas simétricas.

from __future__ import annotations

from dataclasses import dataclass


MIN_INT32 = -(2**31)
MAX_INT32 = 2**31 - 1


@dataclass
class TreeNode:
    val: int
    left: TreeNode | None = None
    right: TreeNode | None = None


class Codec:
    NULL = "#"
    SEP = ","

    def serialize(self, root: TreeNode | None) -> str:
        tokens: list[str] = []

        def visit(node: TreeNode | None) -> None:
            if node is None:
                tokens.append(self.NULL)
                return

            if node.val < MIN_INT32 or node.val > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            tokens.append(str(node.val))
            visit(node.left)
            visit(node.right)

        visit(root)
        return self.SEP.join(tokens)

    def deserialize(self, data: str) -> TreeNode | None:
        if data == "":
            raise ValueError("serialization cannot be empty")

        tokens = iter(data.split(self.SEP))

        def build() -> TreeNode | None:
            try:
                token = next(tokens)
            except StopIteration:
                raise ValueError("serialization is truncated") from None

            if token == self.NULL:
                return None

            try:
                value = int(token)
            except ValueError:
                raise ValueError(f"invalid integer token: {token}") from None

            if value < MIN_INT32 or value > MAX_INT32:
                raise ValueError("node value is outside signed 32-bit range")

            node = TreeNode(value)
            node.left = build()
            node.right = build()
            return node

        root = build()

        try:
            extra = next(tokens)
        except StopIteration:
            return root

        raise ValueError(f"trailing token: {extra}")

Construir una lista de tokens evita la concatenación repetida de cadenas durante la serialización. El decodificador comparte un único iterador entre las llamadas recursivas, de modo que un hijo no vuelve a empezar desde el principio. Comprobar si queda algún token restante tras completar la raíz evita que se acepten entradas con prefijos válidos como 1,#,#,9,#,#.

Paso cuatro: demostrar que la decodificación revierte la serialización.

Usa inducción estructural sobre un árbol T.

• Caso base: si T está vacío, la serialización emite #. El decodificador lee #, retorna None y consume exactamente el único token de ese subárbol.
• Paso inductivo: supongamos que la afirmación se cumple para los subárboles izquierdo y derecho. La serialización emite el valor de la raíz, seguido de la codificación completa izquierda y luego la codificación completa derecha. El decodificador crea la misma raíz, la primera llamada recursiva consume exactamente la codificación izquierda por hipótesis inductiva y la segunda consume exactamente la codificación derecha. Reconstruye la misma forma y valores y se detiene inmediatamente después de T.

Por lo tanto, deserialize(serialize(T)) es estructuralmente igual a T, y cada llamada deja el iterador en el siguiente subárbol no leído. La verificación final de tokens sobrantes asegura que la raíz haya consumido toda la entrada.

Paso cinco: calcular el costo sin ocultar la salida ni la pila.

Ambas operaciones visitan cada nodo real y puntero nulo una vez, por lo que el tiempo es O(n). La salida serializada y la entrada tokenizada son O(n). El árbol reconstruido en sí también es O(n). El uso de la pila de llamadas recursivas es O(h), donde h es la altura del árbol: O(log n) para un árbol balanceado y O(n) para un árbol completamente desbalanceado.

El código recursivo es una buena respuesta para entrevistas cuando la altura está acotada y la claridad es prioritaria. No es seguro para una cadena controlada por un atacante que supere el límite de recursión del entorno de ejecución. En ese caso, usa una pila explícita o una cola por niveles y aplica límites máximos de nodos, tokens, bytes y profundidad.

Paso seis: comparar DFS en preorden con BFS por niveles.

Ambos pueden ser reversibles en tiempo O(n) y espacio de salida si conservan la información de nulos.

BFS es preferible cuando la profundidad de recursión es el riesgo inmediato o el sistema circundante ya utiliza una representación por niveles. El preorden es preferible para la entrevista base porque su gramática y su demostración son más sencillas.

Paso siete: verificar pruebas de ida y vuelta (round-trip) y entradas con formato incorrecto.

Las pruebas de ida y vuelta deben cubrir:

También rechaza "", 1,#, x,#,#, 2147483648,#,# y 1,#,#,2,#,#. Para árboles generados, compara el árbol original y el decodificado recursivamente y afirma serialize(deserialize(serialize(root))) == serialize(root). Una prueba con un árbol desbalanceado debe ejecutarse cerca del límite de altura aceptado para que la suposición sobre la pila sea visible y no accidental.

Respuesta de muestra de alta calidad

«Primero confirmaría que se trata de un árbol binario arbitrario, que los valores son enteros de 32 bits con signo y que el formato solo necesita ser leído por nuestro decodificador. Dado que se permiten valores duplicados, necesito codificar la estructura explícitamente.

Realizaré un recorrido en preorden. Para un nodo real emito su valor, luego sus subárboles izquierdo y derecho; para un hijo ausente emito #. Esto distingue, por ejemplo, un hijo izquierdo de un hijo derecho incluso cuando los valores en preorden son idénticos. Durante la decodificación, un único iterador de tokens compartido refleja la misma gramática: # retorna None; de lo contrario, creo un nodo y construyo recursivamente el izquierdo y luego el derecho.

La corrección se deduce por inducción estructural. El árbol vacío es un #. Para una raíz real, asumiendo que cada llamada recursiva reconstruye y consume exactamente un subárbol hijo, las dos llamadas consumen las partes serializadas izquierda y derecha en orden y reconstruyen la raíz original. Rechazaré la finalización prematura, valores inválidos o fuera de rango y tokens sobrantes.

Cada nodo real y puntero nulo se procesa una vez, por lo que ambas operaciones son O(n). El texto y los tokens usan O(n) de espacio, mientras que la recursión utiliza O(h) de pila. Si la altura del árbol puede ser adversaria, cambiaría a una pila explícita o BFS e impondría límites de tamaño y profundidad. Probaría casos vacíos, de un solo nodo, solo izquierdo frente a solo derecho, duplicados, valores negativos, límites de enteros, cadenas malformadas y pruebas aleatorias de ida y vuelta».

Errores comunes

• Serializar solo los valores de los nodos → distintas formas pueden producir el mismo recorrido → emite marcadores nulos u otro límite estructural explícito.
• Usar un delimitador que pueda aparecer dentro de los valores → los límites de los tokens se vuelven ambiguos → escapa los valores, añade longitudes o elige un delimitador fuera de la gramática de valores.
• Crear un nuevo iterador en cada llamada recursiva → cada hijo vuelve a leer el primer token → comparte un único iterador o índice que avance.
• Decodificar la raíz e ignorar el texto restante → un prefijo válido oculta datos corruptos al final → exige el consumo completo de la entrada.
• Dejar que la falta de un token se manifieste como una excepción no relacionada → los datos truncados son difíciles de diagnosticar → convierte el agotamiento prematuro en un error de análisis sintáctico claro.
• Afirmar que el espacio auxiliar es siempre O(log n) → un árbol desbalanceado tiene una altura n, y la tokenización también usa espacio lineal → separa los costos de salida, almacenamiento de tokens, árbol y pila de llamadas.
• Decir que los valores en preorden son suficientes para un BST sin definir los duplicados → claves iguales pueden hacer que la reconstrucción sea ambigua → especifica el ordenamiento y la política de duplicados antes de eliminar los marcadores.
• Usar código recursivo para profundidades no confiables sin límites → una cadena larga puede agotar la pila → usa una pila explícita y límites de recursos.
• Comparar la identidad de los objetos después de un ciclo de serialización/deserialización → la reconstrucción crea nuevos nodos → compara valores y estructura.
• Probar únicamente un ejemplo balanceado → la ambigüedad izquierda/derecha y el riesgo de pila permanecen ocultos → incluye casos vacíos, unilaterales, duplicados, extremos, malformados y desbalanceados.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Puede un árbol binario de búsqueda omitir los marcadores nulos?

A menudo sí. Con un invariante estricto de BST y claves únicas, el preorden se puede reconstruir manteniendo límites inferior y superior: los valores dentro del rango actual pertenecen a ese subárbol, y el primer valor fuera de él pertenece a un ancestro. Si se permiten duplicados, el contrato debe especificar si los valores iguales van a la izquierda, a la derecha o se contabilizan en el nodo. Sin esa política, el formato compacto es ambiguo. El problema base de árbol arbitrario no puede usar esta optimización.

Pregunta de seguimiento 2: ¿Cómo darías soporte a valores de cadena arbitrarios?

La coma y # pueden aparecer dentro de una cadena, por lo que dividir por delimitadores deja de ser autodelimitante. Una opción es un prefijo de longitud como 5:hello, seguido de etiquetas explícitas de nodo/nulo. Otra es una biblioteca de serialización estándar con un esquema. El uso de secuencias de escape puede funcionar, pero el decodificador debe distinguir los separadores escapados de los estructurales y gestionar secuencias de escape inválidas. Los prefijos de longitud hacen que las reglas de consumo sean más fáciles de demostrar.

Pregunta de seguimiento 3: ¿Qué cambia para un árbol con millones de nodos o una profundidad extrema?

Evita las llamadas recursivas y evita dividir toda la entrada si el consumo máximo de memoria es crítico. Procesa los tokens en flujo mediante un analizador sintáctico iterativo con una pila explícita de posiciones de hijos, y envía la salida a un escritor en lugar de recolectar todos los tokens primero. Aplica límites máximos de bytes, tokens, nodos, longitud de enteros y profundidad antes de asignar estado ilimitado. El tiempo sigue siendo O(n), pero la memoria se ajusta a la pila activa o cola más la política del búfer de salida.

Pregunta de seguimiento 4: ¿Cómo versionarías este formato en un sistema de producción?

Añade un identificador de formato y una versión fuera del contenido útil (payload) del árbol, define el ancho del entero y la codificación de texto, y especifica si los campos o versiones desconocidos fallan cerrando el proceso (fail closed). Incluye una verificación de integridad cuando se deba detectar corrupción, pero no trates una suma de verificación como autenticación. Los despliegues necesitan compatibilidad de lectura de versiones anteriores y escritura de nuevas (read-old/write-new) y casos de prueba fijos (fixtures) para cada versión soportada. Para servicios entre diferentes lenguajes, un formato basado en esquemas con mantenimiento suele ser más seguro que extender el códec de la entrevista.

Pregunta de seguimiento 5: ¿Podría la serialización por niveles recortar de forma segura los nulos finales?

Sí, si el decodificador define las posiciones omitidas después del último nodo real como nulas y el serializador recorta únicamente la secuencia final de marcadores nulos. No debe eliminar un nulo interno porque eso alteraría la alineación de los hijos de los nodos posteriores. El contrato de ida y vuelta y las reglas para entradas malformadas deben probarse después del recorte; que «parezca un arreglo más corto» no es una prueba de equivalencia.