#include <functional>
#include <iostream>
#include <random>

class BinaryTreeNode {
private:
    const int64_t m_value;
    std::unique_ptr<BinaryTreeNode> m_left = {};
    std::unique_ptr<BinaryTreeNode> m_right = {};
public:
    BinaryTreeNode(int64_t value) : m_value{ value } {}

    int64_t value() const { return m_value; }
    const BinaryTreeNode* left() const { return m_left.get(); }
    const BinaryTreeNode* right() const { return m_right.get(); }
    std::unique_ptr<BinaryTreeNode> takeLeft() { return std::move(m_left); }
    std::unique_ptr<BinaryTreeNode> takeRight() { return std::move(m_right); }
public:
    void insert(int64_t value) {
        if (value < m_value) {
            if (m_left) {
                m_left->insert(value);
            } else {
                m_left = std::make_unique<BinaryTreeNode>(value);
            }
        } else if(value > m_value) {
            if (m_right) {
                m_right->insert(value);
            } else {
                m_right = std::make_unique<BinaryTreeNode>(value);
            }
        }
    }
};
class AbstractTreeCrawler {
public:
    virtual ~AbstractTreeCrawler() noexcept = default;
    void travel(const BinaryTreeNode* node) {
        recursiveUseNode(node, 0);
    }
private:
    virtual void recursiveUseNode(const BinaryTreeNode* node, size_t offset) const = 0;
};
class BinarySearchTree {
private:
    std::unique_ptr<BinaryTreeNode> m_head = {};
    size_t m_size = {};
public:
    void insert(int64_t value) {
        if (m_head) {
            m_head->insert(value);
        } else {
            m_head = std::make_unique<BinaryTreeNode>(value);
        }
    }

    void travelBy(std::unique_ptr<AbstractTreeCrawler> crawler) {
        crawler->travel(m_head.get());
    }
};


struct BackwardTraversal : public AbstractTreeCrawler {
private:
    std::function<void(int64_t, size_t)> m_operation;
public:
    BackwardTraversal(std::function<void(int64_t, size_t)> operation): m_operation { std::move(operation) }{}
private:
    virtual void recursiveUseNode(const BinaryTreeNode* node, size_t offset) const override {
        if (node == nullptr)
            return;

        recursiveUseNode(node->left(), offset + 1);
        recursiveUseNode(node->right(), offset + 1);
        m_operation(node->value(), offset);
    }
};
struct SymmetricTraversal : public AbstractTreeCrawler {
private:
    std::function<void(int64_t, size_t)> m_operation;
public:
    SymmetricTraversal(std::function<void(int64_t, size_t)> operation) : m_operation{ std::move(operation) } {}
private:
    virtual void recursiveUseNode(const BinaryTreeNode* node, size_t offset) const override {
        if (node == nullptr)
            return;

        recursiveUseNode(node->left(), offset + 1);
        m_operation(node->value(), offset);
        recursiveUseNode(node->right(), offset + 1);
    }
};
struct ForwardTraversal : public AbstractTreeCrawler {
private:
    std::function<void(int64_t, size_t)> m_operation;
public:
    ForwardTraversal(std::function<void(int64_t, size_t)> operation) : m_operation{ std::move(operation) } {}
private:
    virtual void recursiveUseNode(const BinaryTreeNode* node, size_t offset) const override {
        if (node == nullptr)
            return;

        m_operation(node->value(), offset);
        recursiveUseNode(node->left(), offset + 1);
        recursiveUseNode(node->right(), offset + 1);
    }
};


int main() {
    BinarySearchTree tree_1;
    BinarySearchTree tree_2;
    auto generator = std::bind(std::uniform_int_distribution<int64_t>{ 0, 100 }, std::mt19937{ std::random_device{}() });

    for (int i = 0; i < 10; ++i)
        tree_1.insert(generator());
    for (int i = 0; i < 10; ++i)
        tree_2.insert(generator());


    std::cout << "====================================================" << std::endl;
    tree_1.travelBy(std::make_unique<BackwardTraversal>([](int64_t value, size_t offset) {
        std::cout << std::string(offset, '\t') << value << std::endl;
        }));
    std::cout << "====================================================" << std::endl;
    tree_1.travelBy(std::make_unique<SymmetricTraversal>([](int64_t value, size_t offset) {
            std::cout << std::string(offset, '\t') << value << std::endl;
        }));

    std::cout << "====================================================" << std::endl;
    tree_2.travelBy(std::make_unique<ForwardTraversal>([&tree_1](int64_t value, size_t) {
            tree_1.insert(value);
        }));
    std::cout << "====================================================" << std::endl;
    tree_1.travelBy(std::make_unique<SymmetricTraversal>([](int64_t value, size_t offset) {
        std::cout << std::string(offset, '\t') << value << std::endl;
        }));
    std::cout << "====================================================" << std::endl;
}