Как в двоичном дереве поиска найти минимальный элемент, больший данного?

Question

[Artyom_Kopan]

Моя функция выглядит так (она работает неправильно, если в левом поддереве есть элементы, большие, чем key; Здесь tree->left - левое поддерево, tree->right - правое; Value - пользовательский тип данных; comparator - функция сравнения):

Value getUpperBound(Tree* tree, Value key)
{
    if (!tree)
        return wrapNone();
    return tree->comparator(tree->key, key) > 0 ? tree->key : getUpperBound(tree->right, key);
}

Answer 1

[Wataru]

Надо, как в бинарном поиске - идти или в левое или в правое поддерево. Если пошли в левое поддерево, то надо проверить, что вернула рекурсивная функция - если там не было больших элементов, то надо вернуть значение в текущей вершине.

Comments

[Artyom_Kopan]

А будет ли этот алгоритм работать, например, на таком дереве?
4
2 5
1 10 1 12

Вызываем getUpperBound(3). Идём в левое поддерево - там есть элемент 10, и мы возвращаем его. Но правильный ответ находится в корне дерева - 4

[Alexandroppolus]

Artyom_Kopan, это не дерево поиска.

https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D...

[Artyom_Kopan]

Alexandroppolus, понял, спасибо. Я не учёл, что ВСЕ вершины в левом поддереве должны быть меньше корня