Ytdyklly

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);

}

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.