Nearest Node in a Binary Search Tree

#include <iostream>
#include <cassert>
#include <new>

struct node {
    node * left;
    node * right;
    int value;
};

const node * nearest_node(const node * root, int query) {
    // TODO: Implement this function
    return nullptr;
}

node * add_integer(node * & n, int new_value) {
    if (!n) {
        n = new node{nullptr, nullptr, new_value};
        return n;
    } else if (n->value < new_value) {
        return add_integer(n->right, new_value);
    } else if (n->value > new_value) {
        return add_integer(n->left, new_value);
    } else {
        assert(false && "duplicate value added to tree");
    }
}

void cleanup(const node * n) {
    if (n) {
        cleanup(n->left);
        cleanup(n->right);
        delete n;
    }
}

class tree {
    node * root;

    public:
    tree() : root(nullptr) {}
    ~tree() { cleanup(root); }

    node * add(int new_value) {
        return ::add_integer(root, new_value);
    }

    const node * nearest_node(int query) const {
        return ::nearest_node(root, query);
    }
};

void test_case(const tree & t, int line, int query, const node * expected) {
    std::cout << "At line " << line << ": ";
    std::cout.flush();
    const node * result = t.nearest_node(query);
    if (result == expected) {
        std::cout << "OK" << std::endl;
    } else {
        std::cout << "Expected node { " << expected->value << " }, found node ";
        if (result) {
            std::cout << "{ " << result->value << " }" << std::endl;
        } else {
            std::cout << "nullptr" << std::endl;
        }
    }
}

int main() {
    {
        tree t;
        node* n10 = t.add(10);
        node* n20 = t.add(20);
        node* n30 = t.add(30);
        node* n40 = t.add(40);

        test_case(t, __LINE__, 0, n10);
        test_case(t, __LINE__, 10, n10);
        test_case(t, __LINE__, 14, n10);
        test_case(t, __LINE__, 16, n20);
        test_case(t, __LINE__, 20, n20);
        test_case(t, __LINE__, 24, n20);
        test_case(t, __LINE__, 26, n30);
        test_case(t, __LINE__, 30, n30);
        test_case(t, __LINE__, 34, n30);
        test_case(t, __LINE__, 36, n40);
        test_case(t, __LINE__, 40, n40);
        test_case(t, __LINE__, 100, n40);
    }
    {
        tree t;
        node* n20 = t.add(20);
        node* n10 = t.add(10);
        node* n40 = t.add(40);
        node* n30 = t.add(30);

        test_case(t, __LINE__, 0, n10);
        test_case(t, __LINE__, 10, n10);
        test_case(t, __LINE__, 14, n10);
        test_case(t, __LINE__, 16, n20);
        test_case(t, __LINE__, 20, n20);
        test_case(t, __LINE__, 24, n20);
        test_case(t, __LINE__, 26, n30);
        test_case(t, __LINE__, 30, n30);
        test_case(t, __LINE__, 34, n30);
        test_case(t, __LINE__, 36, n40);
        test_case(t, __LINE__, 40, n40);
        test_case(t, __LINE__, 100, n40);
    }
    {
        tree t;
        node* n20 = t.add(20);
        node* n30 = t.add(30);
        node* n10 = t.add(10);
        node* n40 = t.add(40);

        test_case(t, __LINE__, 0, n10);
        test_case(t, __LINE__, 10, n10);
        test_case(t, __LINE__, 14, n10);
        test_case(t, __LINE__, 16, n20);
        test_case(t, __LINE__, 20, n20);
        test_case(t, __LINE__, 24, n20);
        test_case(t, __LINE__, 26, n30);
        test_case(t, __LINE__, 30, n30);
        test_case(t, __LINE__, 34, n30);
        test_case(t, __LINE__, 36, n40);
        test_case(t, __LINE__, 40, n40);
        test_case(t, __LINE__, 100, n40);
    }
}