Binary Search Tree implementation with unique pointers

Question

I have implemented a binary search tree using templates and unique_ptr in C++ 11. At present, only insertion and deletion are implemented. Please provide your feedback for improvements.

#include <iostream>
#include <memory>


template<typename T>
class Btree {
public:
    void insert(T data)
    {
        _insert(root, data);
    }
    void traverse(void (*func)(T data))
    {
        _traverse(root, func);
    }
    void del(T data)
    {
        _del(root, data);
    }
private:
    struct node {
        T data;
        std::unique_ptr<node> left, right;
        node(T data): data(data), left(nullptr), right(nullptr) {}
    };

    std::unique_ptr<node> root;
    void _insert(std::unique_ptr<node>& curr, T data);
    void _del(std::unique_ptr<node>& curr, T data);
    void _traverse(std::unique_ptr<node>& curr, void (*func)(T data));
    T _findmin(std::unique_ptr<node> &curr);
};

template<typename T>
void Btree<T>::_insert(std::unique_ptr<node>& curr, T data)
{
    if (curr == nullptr) {
        curr.reset(new node(data));
        return;
    }

    if (data < curr->data)
        _insert(curr->left, data);
    else
        _insert(curr->right, data);
}
template<typename T>
T Btree<T>::_findmin(std::unique_ptr<node>& curr)
{
    if (curr && curr->left == nullptr)
        return curr->data;
    return _findmin(curr->left);    
}
template<typename T>
void Btree<T>::_del(std::unique_ptr<node>& curr, T data)
{
    if (curr == nullptr)
        return;
    if (data < curr->data)
        _del(curr->left, data);
    else if (data > curr->data)
        _del(curr->right, data);
    else {
        // if one child is nullptr or both child are nullptr
        if (curr->left == nullptr) {
            auto &p = curr->right;
            curr.reset(p.release());
        }
        else if (curr->right == nullptr) {
            auto &p = curr->left;
            curr.reset(p.release());
        }
        //if child is non leaf node    
        else {
            T temp = _findmin(curr->right);
            curr->data = temp;
            _del(curr->right, temp);
        }
    }
}
template<typename T>
void Btree<T>::_traverse(std::unique_ptr<node>& curr, void (*func)(T data))
{
    if (curr == nullptr)
        return;
    _traverse(curr->left, func);
    func(curr->data);
    _traverse(curr->right, func);
}

Answer 1

Observations

You pass data by value. This is fine for small data types like int. But imagine that T is some huge object that is very expensive to copy. You should think of passing the data by reference to avoid any intermediate copies. When you get a bit more advanced think about passing by r-value reference to allow you to move the objects.

For your traversal you pass a function pointer. This is a bit limiting. Normally you would templateze the function to allow you to pass any function like object (function pointer/functor/lambda/std::function) etc.

Yes you need recursion when traversing trees. But you don't need it everywhere. There are a couple of places where a simple loop would be sufficient.

I can see why you use std::unique_ptr. But in my view a tree is a container and should manage its own memory. So I would have simply used Node* inside data. The code is not that much harder to write in this context. BUT I don't have any real issue with std::unique_ptr.

Code

Insert by const reference

void insert(T const& data)
{
    _insert(root, data);
}
_insert(std::unique_ptr<node>& curr, T const& data)
{
    if (curr.get() == nullptr) {
        curr.reset(new node(data));
        return;
    }

    auto& next = (data < curr->data) ? curr->left : curr->right;
    _insert(next, data);
}

Insert by r-Value reference

void insert(T&& data)
{
    _insert(root, std::forward<T>(data));
}
_insert(std::unique_ptr<node>& curr, T&& data)
{
    if (curr.get() == nullptr) {
        curr.reset(new node(data));
        return;
    }

    auto& next = (data < curr->data) ? curr->left : curr->right;
    _insert(next, std::forward<T>(data));
}

Emplace into node.

// This calls T constructor only when you construct the node itself.
template<typename... Args>
void emplace(Args const&... args)
{
    _emplace(root, args...));
}
template<typename... Args>
_emplace(std::unique_ptr<node>& curr, Args const&... args)
{
    if (curr.get() == nullptr) {
        curr.reset(new node(args...));
        return;
    }

    auto& next = (data < curr->data) ? curr->left : curr->right;
    _insert(next, args...);
}
template<typename... Args>
node::node(Args const&... args)
    : data(args...)  // Data of type T constructed in place
    , left(nullptr)
    , right(nullptr)
{}

Using a function like object to traverse the tree:

template<typename F>
void traverse(const & action)
{
    _traverse(root, action);
}
template<typename F>
void _traverse(std::unique_ptr<node>& curr, F const& action);


// outside class

template<typename T>
template<typename F>
void Btree<T>::_traverse(std::unique_ptr<node>& curr, F const& action)
{
    if (curr == nullptr)
        return;
    _traverse(curr->left, action);
    action(curr->data);
    _traverse(curr->right, action);
}

int main()
{
     Btree<int>  tree;
     tree.traverse([](int x){std::cout << x << " ";});
}

Answer 2

Since insert gets its data by value, you're making multiple copies of that data as you navigate down the tree to find where to add the new node. Passing the parameter by const T& (so you only make one copy) would avoid these copies, a benefit for types that are expensive to copy. Another possibility is to use T && to move the data, but this will change the original value being passed in which may be undesirable.

The value passed to the function called by _traverse is also copied. Depending on your needs, this could also use a const T &, or overloads of _traverse that take func with a reference could be provided. The downside to providing access to the data via a reference is that it can allow that data to be altered.

If _insert takes curr as a pointer (std::unique_ptr<node>* curr) then you can use a loop rather than recursion. This also applies to _findmin and _del.