Создание узла бинарного поискового дерева

Условие

Требуется реализовать структуру данных, представляющую узел бинарного дерева поиска, содержащий значение типа int.

Ответ

Узел бинарного дерева поиска хранит значение и ссылки на левое и правое поддерево. Сам узел не обеспечивает порядок: его должны сохранять операции вставки и удаления.

Вариант с единоличным владением потомками:

#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(int v) : value(v) {}
};

Для дерева без повторов все значения слева меньше value, справа — больше. Правило для дубликатов задаётся отдельно. unique_ptr автоматически освобождает поддеревья; если нужны невладеющие связи с родителем, нельзя создавать ими циклическое владение.