How to find the minimum element greater than a given one in a binary search tree?

Question

Algorithms

My function looks like this (it does not work correctly if there are elements in the left subtree greater than key; Here tree->left is the left subtree, tree->right is the right one; Value is a custom data type; comparator is a comparison function):

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

It is necessary, as in binary search - to go either to the left or to the right subtree. If we went to the left subtree, then we need to check what the recursive function returned - if there were no large elements, then we need to return the value at the current vertex.