Неправильная работа двоичного дерева поиска

Всем привет! Я тут хотел написать двоичное дерево поиска на C++, но возникли непонятные мне проблемы. Всё просто: нужно реализовать двоичное дерево поиска со следующими командами: insert x - вставка элемента, exists x - проверка на наличие элемента в дереве (true / false), delete x - удаление элемента (если элемента нет, то делать ничего не нужно), next x - вывод минимального элемента, строго большего некоторого x (none, если такого нет) и prev x - вывод максимального элемента, строго меньшего некоторого x (none, если такого нет). К сожалению, моя программа падает на тестах (тесты я назвать не могу) и, вроде как, выводит неправильный ответ. Помогите, пожалуйста, найти ошибку в моем коде. Если вы можете придумать тест, на котором она валится, то поделитесь им, пожалуйста, со мной.

#include <fstream>

using namespace std;

struct Node {
    int value = 0;
    Node *left = nullptr;
    Node *right = nullptr;
};

Node *getMaxNode(Node *&cur_node) {
    while (cur_node->right != nullptr) {
        cur_node = cur_node->right;
    }

    return cur_node;
}

Node *addNode(int value) {
    Node *new_node = new Node;
    new_node->value = value;
    return new_node;
}

void insertNode(Node *&root, int value) {
    if (root == nullptr) {
        root = addNode(value);
        return;
    }

    if (value < root->value) {
        insertNode(root->left, value);
    } else {
        insertNode(root->right, value);
    }
}

bool containsNode(Node *&root, int value) {
    if (root == nullptr) {
        return false;
    }

    if (root->value == value) {
        return true;
    }

    if (value < root->value) {
        return containsNode(root->left, value);
    } else {
        return containsNode(root->right, value);
    }
}

void removeNode(Node *&root, int value) {
    if (root == nullptr) {
        return;
    }

    if (value < root->value) {

        removeNode(root->left, value);

    } else if (value > root->value) {

        removeNode(root->right, value);

    } else if (value == root->value) {

        if (root->left == nullptr && root->right == nullptr) {

            root = nullptr;

        } else if (root->left == nullptr) {

            Node *cur_node = root;
            root = root->right;
            delete cur_node;

        } else if (root->right == nullptr) {

            Node *cur_node = root;
            root = root->left;
            delete cur_node;

        } else {

            Node *cur_node = getMaxNode(root->left);
            root->value = cur_node->value;
            removeNode(root->left, cur_node->value);
        }

    }
}

Node *nextValue(Node *cur_node, int value) {
    Node *min = nullptr;

    while (cur_node != nullptr) {
        if (cur_node->value > value) {
            min = cur_node;
            cur_node = cur_node->left;
        } else {
            cur_node = cur_node->right;
        }
    }
    return min;
}

Node *prevValue(Node *cur_node, int value) {
    Node *max = nullptr;

    while (cur_node != nullptr) {
        if (cur_node->value < value) {
            max = cur_node;
            cur_node = cur_node->right;
        } else {
            cur_node = cur_node->left;
        }
    }
    return max;
}

int main() {
    ifstream in;
    in.open("bstsimple.in");

    ofstream out;
    out.open("bstsimple.out");

    Node *root = nullptr;

    while (!in.eof()) {
        string command;
        int x;
        in >> command >> x;

        if (command == "insert") {

            insertNode(root, x);

        } else if (command == "delete") {

            removeNode(root, x);

        } else if (command == "exists") {

            if (containsNode(root, x)) {
                out << "true" << endl;
            } else {
                out << "false" << endl;
            }

        } else if (command == "next") {

            Node *min = nextValue(root, x);

            if (min != nullptr) {
                out << min->value << endl;
            } else {
                out << "none" << endl;
            }

        } else if (command == "prev") {

            Node *max = prevValue(root, x);

            if (max != nullptr) {
                out << max->value << endl;
            } else {
                out << "none" << endl;
            }
        }
    }

    in.close();
    out.close();

    return 0;
}