El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Ejercicios con Árboles

Siguiente ►
►

Módulo cargado: árboles genéricos y su terminología (06-01), árboles binarios y sus cuentas (06-02), los cuatro recorridos (06-03), el ABB con rangos (06-04), el AVL que no degenera (06-05), el árbol B de las bases de datos (06-06) y el montículo que abrió heapq (06-07). Esta lección no añade teoría: es el gimnasio donde esas piezas se combinan sobre TaskFlow en seis ejercicios progresivos — de calentar con recorridos a tres clásicos absolutos de entrevista técnica (validar un ABB con su trampa célebre, reconstruir un árbol desde sus recorridos, y el top-k con montículo de tamaño k). Intenta cada uno en serio antes de mirar la solución: el enunciado incluye pistas, y pelearse diez minutos con un árbol enseña más que leer diez soluciones.

Contenido

  1. Ejercicio 1: radiografía del árbol de proyectos (altura y conteo)
  2. Ejercicio 2: auditar la propiedad ABB (con la trampa clásica)
  3. Ejercicio 3: la k-ésima tarea más prioritaria (inorden parcial)
  4. Ejercicio 4: presupuesto por subárbol (postorden)
  5. Ejercicio 5: reconstruir un árbol desde preorden + inorden
  6. Ejercicio 6: top-k urgentes con montículo de tamaño k
  7. Soluciones comentadas

Los datos de partida

Todos los ejercicios usan las clases del módulo: NodoArbol (06-01, con valor y lista hijos), NodoBinario (06-02), ArbolBusqueda/NodoABB (06-04) y Monticulo (06-07). Para los dos primeros ejercicios sobre árbol genérico, este proyecto:

def T(id, titulo, prioridad, horas):
    return {"id": id, "titulo": titulo, "prioridad": prioridad,
            "estado": "pendiente", "horas": horas}

proyecto = NodoArbol(T(1, "Lanzar TaskFlow 2.0", 1, 8))
backend = proyecto.agregar_hijo(NodoArbol(T(2, "Backend", 1, 5)))
frontend = proyecto.agregar_hijo(NodoArbol(T(3, "Frontend", 2, 3)))
docs = proyecto.agregar_hijo(NodoArbol(T(4, "Documentacion", 3, 6)))
api = backend.agregar_hijo(NodoArbol(T(5, "API v2", 1, 12)))
bd = backend.agregar_hijo(NodoArbol(T(6, "Migrar BD", 2, 9)))
api.agregar_hijo(NodoArbol(T(7, "Autenticacion", 1, 4)))
frontend.agregar_hijo(NodoArbol(T(8, "Rediseno panel", 2, 10)))
graph TD
    A["1: Lanzar 2.0 (8h)"] --> B["2: Backend (5h)"]
    A --> C["3: Frontend (3h)"]
    A --> D["4: Documentacion (6h)"]
    B --> E["5: API v2 (12h)"]
    B --> F["6: Migrar BD (9h)"]
    E --> G["7: Autenticacion (4h)"]
    C --> H["8: Rediseno panel (10h)"]

Ejercicios

Ejercicio 1: radiografía del árbol de proyectos

Escribe dos funciones sobre el árbol genérico: altura_generico(nodo) (altura del subárbol, con la convención del módulo: vacío = −1, hoja = 0) y contar_por_nivel(raiz) (un dict nivel → número de nodos). Para proyecto deben dar altura 3 y {0: 1, 1: 3, 2: 3, 3: 1}. Pista: la primera pide postorden (la altura sube de hijos a padres); la segunda sale sola con el recorrido por niveles de 06-03 o con un preorden que arrastre la profundidad.

Ejercicio 2: auditar la propiedad ABB

Escribe es_abb(nodo) que decida si un árbol binario (nodos con clave) cumple la propiedad de búsqueda. Empieza escribiendo la versión incorrecta — la que solo compara cada nodo con sus hijos directos — y encuentra un árbol que la engañe; después escribe la correcta propagando cotas (minimo, maximo). Árbol de prueba obligatorio:

graph TD
    A((10)) --> B((5))
    A --> C((15))
    B --> D((3))
    B --> E((12))

Cada padre es mayor que su hijo izquierdo y menor que el derecho... y sin embargo no es un ABB. ¿Por qué?

Ejercicio 3: la k-ésima tarea más prioritaria

Sobre el índice AVL/ABB por clave (prioridad, id) de 06-04/06-05, escribe k_esima(arbol, k) que devuelva la tarea que ocupa la posición k (1-indexada) en orden de urgencia — sin materializar la lista completa: el inorden debe detenerse en cuanto encuentra la k-ésima. Pista: un contador que viaja por la recursión y un valor de retorno que corta la exploración (el mismo patrón de parada temprana que profundidad_de en 06-01).

Ejercicio 4: presupuesto por subárbol

Sobre el árbol proyecto, escribe presupuestar(nodo) que devuelva un dict id → horas acumuladas de su subárbol (las propias más todos los descendientes) en una sola pasada O(n). Para la raíz debe salir 57; para Backend (id 2), 30. Pista: postorden puro — es horas_acumuladas de 06-03 generalizada a n hijos, guardando además cada resultado intermedio.

Ejercicio 5: reconstruir un árbol desde preorden + inorden

Un compañero exportó un árbol binario de TaskFlow como dos listas: preorden = [10, 6, 3, 8, 15, 12, 20] e inorden = [3, 6, 8, 10, 12, 15, 20]. Escribe reconstruir(preorden, inorden) que devuelva la raíz del único árbol binario compatible con ambas (claves sin duplicados). Pistas: la primera clave del preorden es siempre la raíz (06-03); su posición en el inorden parte esa lista en subárbol izquierdo y derecho; recursión sobre las mitades. Pregunta extra: ¿por qué preorden solo no basta?

Ejercicio 6: top-k urgentes con montículo de tamaño k

TaskFlow archiva cientos de miles de tareas y el panel solo muestra las k más urgentes (menor (prioridad, id)). Ordenar todo cuesta O(n log n) y materializa lo que no se ve. Escribe top_k(tareas, k) — con tareas un iterable de dicts — que lo haga en O(n log k) manteniendo un montículo de tamaño k como máximo. Pista: si el heap es un min-heap, ¿qué debe vivir en su raíz para poder decidir en O(1) si una tarea nueva entra en el top? (Repasa la nota max-heap de 06-07: negar es tu amiga.)

Soluciones

Solución 1: radiografía del árbol

def altura_generico(nodo):
    if nodo is None:
        return -1
    if not nodo.hijos:                     # hoja: altura 0
        return 0
    return 1 + max(altura_generico(h) for h in nodo.hijos)

from collections import deque

def contar_por_nivel(raiz):
    conteo = {}
    cola = deque([(raiz, 0)])              # viajamos con la profundidad, como en 06-03
    while cola:
        nodo, nivel = cola.popleft()
        conteo[nivel] = conteo.get(nivel, 0) + 1
        for h in nodo.hijos:
            cola.append((h, nivel + 1))
    return conteo

print(altura_generico(proyecto))     # 3
print(contar_por_nivel(proyecto))    # {0: 1, 1: 3, 2: 3, 3: 1}

Comentario: altura_generico generaliza la altura binaria de 06-02 cambiando max(izq, der) por max sobre la lista de hijos — y necesita el caso hoja explícito, porque max() sobre una secuencia vacía lanza ValueError (en la versión binaria lo tapaba el -1 de los hijos None). La información fluye de hijos a padres: postorden. contar_por_nivel fluye al revés (la profundidad baja de padres a hijos) y por eso encaja el BFS con tupla (nodo, nivel) — el deque del módulo 4 una vez más; con defaultdict(int) del módulo 5 la línea del conteo quedaría aún más limpia. Dos preguntas, dos direcciones del flujo, dos recorridos: elegir recorrido es responder "¿hacia dónde fluye la información?".

Solución 2: auditar la propiedad ABB

La versión ingenua y su contraejemplo:

def es_abb_MAL(nodo):
    """INCORRECTA: solo compara con los hijos directos."""
    if nodo is None:
        return True
    if nodo.izquierdo and nodo.izquierdo.clave >= nodo.clave:
        return False
    if nodo.derecho and nodo.derecho.clave <= nodo.clave:
        return False
    return es_abb_MAL(nodo.izquierdo) and es_abb_MAL(nodo.derecho)

# El árbol del enunciado: 10 -> (5 -> (3, 12), 15)
raiz = NodoBinario(10); raiz.clave = 10        # o usa NodoABB directamente
# ... (construcción análoga con clave en cada nodo)
print(es_abb_MAL(raiz))    # True  <- ¡mentira!

El 12 es hijo derecho de 5 (12 > 5: la versión ingenua aplaude) pero vive en el subárbol izquierdo de 10, donde todo debe ser < 10. La propiedad ABB habla de subárboles enteros, no de parejas padre-hijo — la advertencia repetida desde 06-04, y la diferencia exacta con el heap, cuya propiedad sí es local (por eso es_min_heap de 06-07 comparaba solo con el padre y era correcta). La versión buena propaga el rango permitido:

def es_abb(nodo, minimo=float("-inf"), maximo=float("inf")):
    """Cada descenso ESTRECHA el intervalo (minimo, maximo) permitido."""
    if nodo is None:
        return True
    if not (minimo < nodo.clave < maximo):
        return False
    return (es_abb(nodo.izquierdo, minimo, nodo.clave) and
            es_abb(nodo.derecho, nodo.clave, maximo))

print(es_abb(raiz))    # False: al llegar al 12, el intervalo era (-inf, 10) — pero 5 < 12

Comentario: al bajar a la izquierda, el nodo actual se convierte en techo (maximo); a la derecha, en suelo (minimo). El 12 se evalúa con el intervalo (5, 10) heredado de sus dos ancestros y suspende. Una pasada O(n), y el candidato número uno a pregunta de entrevista sobre árboles. Alternativa igual de válida: generar el inorden y comprobar que sale estrictamente creciente — mismo coste, aunque la de cotas corta antes al primer fallo.

Solución 3: la k-ésima tarea

def k_esima(arbol, k):
    def inorden_parcial(nodo, restantes):
        """Devuelve (tarea encontrada o None, cuantas quedan por saltar)."""
        if nodo is None:
            return None, restantes
        # 1) primero, todo el subárbol izquierdo (los más urgentes)
        encontrada, restantes = inorden_parcial(nodo.izquierdo, restantes)
        if encontrada is not None:
            return encontrada, 0                   # ya está: propagar sin mirar más
        # 2) el propio nodo consume un puesto
        restantes -= 1
        if restantes == 0:
            return nodo.valor, 0
        # 3) solo si aún falta, el subárbol derecho
        return inorden_parcial(nodo.derecho, restantes)

    return inorden_parcial(arbol.raiz, k)[0]

# Con el índice de 30 tareas de 06-05 (prioridades (i % 3) + 1):
print(k_esima(indice, 1)["id"])    # 3  (la primera de prioridad 1)
print(k_esima(indice, 11)["id"])   # 1  (la primera de prioridad 2)

Comentario: es el inorden de 06-03 con dos añadidos: un contador restantes que viaja y se descuenta en el paso "visitar nodo", y la propagación inmediata del hallazgo que evita explorar los subárboles pendientes — la parada temprana de profundidad_de (06-01). Coste: O(altura + k) — para k pequeño sobre un AVL, logarítmico, frente al O(n) de materializar en_orden() completo y indexar. Nota de arquitecto: los árboles de las librerías serias ofrecen esta operación en O(log n) puro guardando en cada nodo el tamaño de su subárbol (para saltar subárboles enteros contando en vez de recorriendo); la idea de anotar los nodos con datos agregados es exactamente la del siguiente ejercicio.

Solución 4: presupuesto por subárbol

def presupuestar(nodo, resultado=None):
    """dict id -> horas acumuladas del subarbol. Una pasada, O(n)."""
    if resultado is None:
        resultado = {}
    total = nodo.valor["horas"]                    # las horas propias...
    for h in nodo.hijos:
        presupuestar(h, resultado)                 # (los hijos rellenan lo suyo)
        total += resultado[h.valor["id"]]          # ...mas el acumulado de cada hijo
    resultado[nodo.valor["id"]] = total
    return resultado

presupuesto = presupuestar(proyecto)
print(presupuesto[1])   # 57  (todo el lanzamiento)
print(presupuesto[2])   # 30  (Backend: 5 + (12+4) + 9)
print(presupuesto[5])   # 16  (API v2: 12 + 4)

Comentario: postorden de manual — un padre no puede conocer su total hasta que cada hijo ha depositado el suyo en resultado, así que la recursión sobre los hijos va antes de la suma final. La finura está en reutilizar los acumulados de los hijos (resultado[h.valor["id"]]) en vez de recalcular su subárbol: cada nodo se visita una vez y el coste es O(n); la variante ingenua que llama a "sumar subárbol" para cada nodo repite trabajo y escala a O(n²) en árboles profundos — la misma trampa altura-por-nodo que evitamos en _altura_y_validez (06-05). Con este dict, el gestor de TaskFlow responde "¿cuánto cuesta Backend con todo lo que cuelga?" en O(1): un índice hash del módulo 5 alimentado por un recorrido del módulo 6, trabajando en equipo.

Solución 5: reconstruir desde preorden + inorden

def reconstruir(preorden, inorden):
    if not preorden:
        return None
    raiz = NodoBinario(preorden[0])            # preorden: la raiz SIEMPRE va primero
    corte = inorden.index(preorden[0])         # su posicion parte el inorden en dos
    izq_in, der_in = inorden[:corte], inorden[corte + 1:]
    izq_pre = preorden[1:1 + len(izq_in)]      # el preorden se parte por TAMANO
    der_pre = preorden[1 + len(izq_in):]
    raiz.izquierdo = reconstruir(izq_pre, izq_in)
    raiz.derecho = reconstruir(der_pre, der_in)
    return raiz

arbol = reconstruir([10, 6, 3, 8, 15, 12, 20], [3, 6, 8, 10, 12, 15, 20])
# Verificacion: regenerar ambos recorridos con las funciones de 06-03
pre, ino = [], []
def rec_pre(n):
    if n: pre.append(n.valor); rec_pre(n.izquierdo); rec_pre(n.derecho)
def rec_ino(n):
    if n: rec_ino(n.izquierdo); ino.append(n.valor); rec_ino(n.derecho)
rec_pre(arbol); rec_ino(arbol)
print(pre)   # [10, 6, 3, 8, 15, 12, 20]  — coincide
print(ino)   # [3, 6, 8, 10, 12, 15, 20]  — coincide: es el arbol de 06-03/06-04

Comentario: cada recorrido aporta la mitad de la información — el preorden dice quién manda (su primer elemento es la raíz), el inorden dice quién queda a cada lado (lo anterior a la raíz es su subárbol izquierdo). Sabido el tamaño del lado izquierdo por el inorden, el preorden se parte en las mismas proporciones y la recursión hace el resto. Respuesta a la pregunta extra: preorden solo no determina el árbol — [2, 1] puede ser "2 con hijo izquierdo 1" o "2 con hijo derecho 1"; hace falta el inorden para desambiguar (o saber que el árbol es un ABB, en cuyo caso el inorden es gratis: ¡es el preorden ordenado!). Afinado de profesional: inorden.index(...) es O(n) en cada llamada (O(n²) total en el peor caso); con un dict valor → posición construido una vez — módulo 5 al rescate otra vez — la reconstrucción entera baja a O(n).

Solución 6: top-k urgentes

def top_k(tareas, k):
    """Las k tareas con menor (prioridad, id), ordenadas. O(n log k)."""
    heap = Monticulo()          # min-heap de claves NEGADAS => max-heap de urgencia
    for t in tareas:
        clave = (-t["prioridad"], -t["id"], t)     # negar: la PEOR del top queda en la raiz
        if len(heap) < k:
            heap.insertar(clave)
        elif clave > heap.ver_minimo():            # ¿mas urgente que la peor guardada?
            heap.extraer_minimo()                  # fuera la peor...
            heap.insertar(clave)                   # ...dentro la nueva. O(log k)
    resultado = []
    while len(heap):
        resultado.append(heap.extraer_minimo()[2]) # salen de peor a mejor...
    resultado.reverse()                            # ...invertir: de mejor a peor
    return resultado

import random
tareas = [{"id": i, "titulo": f"Tarea {i}", "prioridad": random.randint(1, 5),
           "estado": "pendiente"} for i in range(1, 100001)]
random.shuffle(tareas)
for t in top_k(tareas, 5):
    print(t["prioridad"], t["id"])    # las 5 de prioridad 1 con menor id, en orden

Comentario: la idea que hay que interiorizar — para retener los k menores, el montículo guarda como mucho k elementos y su raíz es el peor de los buenos (el mayor del top actual), gracias a la negación de claves de 06-07: min-heap de negados = max-heap de originales. Así, cada tarea nueva se compara en O(1) contra ese umbral vivo: si no lo mejora, ni entra (el caso masivamente más frecuente); si lo mejora, un extraer + insertar en O(log k). Total O(n log k) con memoria O(k): con n = 100 000 y k = 5, unas cuentas de nada frente a ordenar cien mil tareas para pintar cinco. Es el patrón exacto de cualquier "top 10" sobre un flujo que no cabe (o no compensa) ordenar — y la pareja (-prioridad, -id) garantiza además el desempate correcto: entre iguales en prioridad gana el id menor.

Errores Comunes y Consejos

  • Validar el ABB contra el padre y quedarse tan ancho (ejercicio 2): el error está tan extendido que los entrevistadores construyen a propósito el árbol del 12. Cotas heredadas o inorden creciente; no hay tercera vía.
  • Recalcular subárboles en vez de reutilizar acumulados (ejercicios 1 y 4): llamar a "altura/suma del subárbol" dentro de cada nodo dispara el coste a O(n²). La información que fluye de hijos a padres se calcula una vez, en postorden, y se guarda.
  • Olvidar la parada temprana en búsquedas recursivas (ejercicio 3): sin propagar el hallazgo, el recorrido sigue visitando subárboles enteros para nada — correcto pero O(n), que era justo lo prohibido.
  • Partir mal las listas al reconstruir (ejercicio 5): el inorden se parte por posición de la raíz; el preorden, por tamaño del lado izquierdo. Cruzar los criterios produce árboles fantasma que luego no reproducen los recorridos — verifica siempre regenerándolos.
  • Usar un min-heap de claves sin negar para el top-k de menores (ejercicio 6): te deja en la raíz al mejor, que es exactamente el que no quieres expulsar. Para retener los k menores se expulsa al mayor: max-heap (negación) obligatorio.
  • Consejo final: los seis ejercicios caben en un mismo fichero con las clases del módulo; guárdalo. El validador, la reconstrucción y el top-k son los tres árboles más preguntados en entrevistas, y presupuestar + k_esima volverán como piezas de los proyectos del módulo 8.

Conclusión

Fin del módulo 6, y el botín es serio: TaskFlow tiene jerarquía real de proyectos con presupuestos por subárbol, un índice ordenado por (prioridad, id) que responde rangos y k-ésimos sin despeinarse (y que, gracias al AVL, no se degrada aunque los ids lleguen ordenados), la certeza de qué hace su base de datos por debajo (B+), y una bandeja de urgencias O(log n) cuyo motor ya no tiene secretos. Y tú tienes el criterio: la pregunta decide la estructura — clave exacta al hash, orden y rangos al árbol equilibrado, "el siguiente más urgente" al montículo, disco al árbol B. Pero fíjate en el supuesto silencioso que ha sostenido todo el módulo: cada nodo tiene exactamente un padre. La subtarea pertenece a una tarea, la tarea a una categoría, y esa unicidad es la que hizo posibles los recorridos sin visitados, la recursión limpia, el equilibrio. Ahora piensa en las dependencias reales de TaskFlow: "desplegar la API" no puede empezar hasta terminar "migrar la BD" y "configurar el servidor" — una tarea que depende de varias a la vez, y quizá otras dos dependen de ella. Eso ya no es un árbol: los caminos se cruzan, aparecen los ciclos posibles (¿A depende de B que depende de A?), y la jerarquía se queda corta. Hace falta la estructura más general del curso, aquella de la que el árbol era solo un caso particular bien educado: el grafo. En el módulo 7 nos esperan su representación, el BFS y el DFS que llevamos dos módulos sembrando — con el conjunto visitados prometido en el módulo 5 por fin en acción — y los caminos mínimos. Nos vemos entre nodos y aristas.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados