Наименьший общий предок

Урок 14 из 16 курса AVL-дерево — Серия «Структуры данных» №10 на Coddy.

Наименьший общий предок двух значений — это самый глубокий узел, в поддереве которого находятся оба этих значения. В бинарном дереве поиска его можно найти, даже не сравнивая поддеревья напрямую: начиная с корня, если оба значения меньше текущего узла, ответ находится где-то в левом поддереве; если оба больше — в правом поддереве.

В тот момент, когда два значения оказываются по разные стороны (или одно из них равно текущему узлу), вы нашли точку разделения: этот узел и является наименьшим общим предком.

Задание

Легко

Напишите функцию lca(tree, p, q), которая возвращает значение наименьшего общего предка для p и q. Вы можете предположить, что оба значения существуют в дереве.

Попробуйте сами

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