Menor Ancestral Comum

Lição 14 de 16 do curso Árvore AVL - Série de Estruturas de Dados #10 da Coddy.

O menor ancestral comum de dois valores é o nó mais profundo que tem ambos em algum lugar de sua subárvore. Em uma árvore binária de busca, você pode encontrá-lo sem nunca comparar as subárvores diretamente: começando pela raiz, se ambos os valores forem menores que o nó atual, a resposta está em algum lugar na subárvore esquerda; se ambos forem maiores, está na subárvore direita.

No momento em que os dois valores caem em lados diferentes (ou um deles é igual ao nó atual), você encontrou o ponto de divisão: esse nó é o menor ancestral comum.

Desafio

Fácil

Escreva uma função lca(tree, p, q) que retorne o valor do ancestral comum mais baixo de p e q. Você pode assumir que ambos os valores existem na árvore.

Experimente você mesmo

#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;
}