Antenato comune più basso

Lezione 14 di 16 del corso Albero AVL - Serie sulle strutture dati #10 di Coddy.

Il antenato comune più basso di due valori è il nodo più profondo che ha entrambi da qualche parte nel suo sottoalbero. In un albero binario di ricerca, puoi trovarlo senza mai confrontare direttamente i sottoalberi: partendo dalla radice, se entrambi i valori sono minori del nodo corrente, la risposta si trova da qualche parte nel sottoalbero sinistro; se sono entrambi maggiori, si trova nel sottoalbero destro.

Nel momento in cui i due valori si trovano su lati diversi (o uno dei due è uguale al nodo corrente), hai trovato il punto di separazione: quel nodo è l'antenato comune più basso.

Sfida

Facile

Scrivi una funzione lca(tree, p, q) che restituisca il valore del più basso antenato comune di p e q. Puoi supporre che entrambi i valori esistano nell'albero.

Provalo tu

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