Ancestro común más bajo

Lección 14 de 16 del curso Árbol AVL - Serie de Estructuras de Datos #10 de Coddy.

El ancestro común más bajo de dos valores es el nodo más profundo que tiene a ambos en algún lugar de su subárbol. En un árbol binario de búsqueda, puedes encontrarlo sin comparar nunca los subárboles directamente: comenzando desde la raíz, si ambos valores son menores que el nodo actual, la respuesta está en algún lugar del subárbol izquierdo; si ambos son mayores, está en el subárbol derecho.

En el momento en que los dos valores caen en lados diferentes (o uno de ellos es igual al nodo actual), has encontrado el punto de división: ese nodo es el ancestro común más bajo.

Desafío

Fácil

Escribe una función lca(tree, p, q) que devuelva el valor del ancestro común más bajo de p y q. Puedes asumir que ambos valores existen en el árbol.

Pruébalo tú mismo

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "avltree.h"
#include "solution.h"

int main(void) {
    AVLTree* tree = AVLTree_create();
    char line1[4096];
    fgets(line1, sizeof(line1), stdin);
    char* tok = strtok(line1, " \n");
    while (tok != NULL) {
        AVLTree_insert(tree, atoi(tok));
        tok = strtok(NULL, " \n");
    }
    char line2[256];
    fgets(line2, sizeof(line2), stdin);
    int p0 = atoi(strtok(line2, " \n"));
    int p1 = atoi(strtok(NULL, " \n"));
    int result = lca(tree, p0, p1);
    printf("%d\n", result);
    return 0;
}