Преемник значения

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

Следующий элемент (in-order successor) для заданного значения — это наименьшее значение в дереве, которое строго больше него; это значение, которое следовало бы сразу за ним в отсортированном списке. Если значение является максимальным в дереве, у него нет следующего элемента.

Его можно найти за один проход, ничего не сортируя: спускайтесь от корня и каждый раз, когда вы делаете шаг вправо, проходя мимо слишком маленького значения, запоминайте последний узел, от которого вы повернули налево, как лучший найденный вариант.

Задание

Легко

Напишите функцию successor(tree, value), которая возвращает наименьшее значение в дереве, строго большее чем value, или -1, если такого значения не существует.

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

#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 result = successor(tree, p0);
    printf("%d\n", result);
    return 0;
}