A binary search tree

bst.cpp

#include <initializer_list>
#include <type_traits>
#include <memory>
#include <iostream>

template <class T>
using ref_ptr = std::decay_t<T>*&;

template <class>
struct Node;

template <class T>
class binary_search_tree
{
    class iterator;
    class impl;
public:
    binary_search_tree();
    binary_search_tree(std::initializer_list<T>);
    binary_search_tree(binary_search_tree<T> const&);
    binary_search_tree(binary_search_tree<T>     &&);
public:
    template <class C>
    void push_back(C&&);
    
    iterator begin()
    {
        Node<T> *node = root;
        while (node->m_left)
            node = node->m_left;
        return node;
    }
    
    iterator end()
    { return nullptr; }
public:
    typedef T              value_type;
    typedef T&             reference;
    typedef iterator const const_iterator;
    typedef T const&       const_reference;
    
    void display() { display(root); }
    void display(Node<T>* node)
    {
        if (node)
        {
            display(node->m_left);
            std::cout<<node->m_value<<" ";
            display(node->m_right);
        }
    }
private:
    std::unique_ptr<impl> m_impl;
    Node<T>* root;
private:
    void internal_copy(binary_search_tree<T> const& other)
    { m_impl->internal_copy(*this, other.root); }
};

template <class T>
binary_search_tree<T>::binary_search_tree()
    : m_impl(std::make_unique<impl>())
    , root{nullptr}
{ }

template <class T>
binary_search_tree<T>::binary_search_tree(std::initializer_list<T> list)
    : binary_search_tree()
{
    for (auto&& x : list)
        push_back(std::forward<decltype(x)>(x));
}

template <class T>
binary_search_tree<T>::binary_search_tree(binary_search_tree<T> const& other)
    : binary_search_tree()
{
    internal_copy(other);
}

template <class T>
binary_search_tree<T>::binary_search_tree(binary_search_tree<T>&& other)
    : binary_search_tree()
{
    internal_copy(other);
}

template <class T>
template <class C>
void binary_search_tree<T>::push_back(C&& value)
{
    m_impl->push_back(std::forward<C>(value), root);
}

template <class T>
struct Node
{
    Node() = default;
    
    template <class Ti>
    Node(Ti&& value, Node *left = nullptr, Node *right = nullptr)
        : m_value(std::forward<Ti>(value))
        , m_left{left}
        , m_right{right}
    { }
    
    friend class binary_search_tree<T>;
private:
    T m_value;
    Node *m_left, *m_right;
};

template <class T, class... Args>
Node<T>* make_node(Args&&... args)
{
    return new Node<T>(std::forward<Args>(args)...);
}

template <class T>
class binary_search_tree<T>::impl
{
public:
    friend binary_search_tree<T>;
private:
    void internal_copy(binary_search_tree<T>&, Node<T>*);

    template <class C>
    void push_back(C&&, ref_ptr<Node<T>>);
    
    template <class F>
    void inorder_traversal(Node<T>* node, F&& f);
};

template <class T>
void binary_search_tree<T>::impl::internal_copy(binary_search_tree<T>& tree, Node<T>* node)
{
    inorder_traversal(node, [&] (auto& value) { tree.push_back(value); });
}

template <class T>
template <class C>
void binary_search_tree<T>::impl::push_back(C&& value, ref_ptr<Node<T>> node)
{
    if (!node)
        node = make_node<T>(std::forward<C>(value));
    else
    {
        if (value < node->m_value)
            push_back(std::forward<C>(value), node->m_left);
        else if (value > node->m_value)
            push_back(std::forward<C>(value), node->m_right);
    }
}

template <class T>
template <class F>
void binary_search_tree<T>::impl::inorder_traversal(Node<T>* node, F&& f)
{
    if (node)
    {
        inorder_traversal(node->m_left, f);
        f(node->m_value);
        inorder_traversal(node->m_right, f);
    }
}

template <class T>
class binary_search_tree<T>::iterator
{
public:
    iterator(Node<T> *node = nullptr) : m_node{node}
    { }
    
    iterator& operator++() 
    
    T&       operator*()       { return *m_node; }
    T const& operator*() const { return *m_node; }
private:
    Node<T> *m_node;
};

template class binary_search_tree<int>;

int main()
{
    binary_search_tree<int> v{6, 3, 84, 24, 882, 9, 295, 56};
    v.display();
}