Set class with binary search tree implementation

Here is my Set implementation with binary search tree that compiles. Please let me know what changes are needed to make it better. Thank you.

```
#include

using namespace std;

template class Set;
template class Node_Iterator;

template
struct Node_Set
{
Node_Set(const T& data)
{
_value = data;
_left = NULL;
_right = NULL;
_friend = NULL;
}

~Node_Set()
{
delete _left;
delete _right;
}

T _value;
Node_Set *_left;
Node_Set *_right;
Node_Set *_friend; // in-order traversal
};

template
class Set
{
public :
Set()
{
_size = 0;
_root = NULL;
}

~Set()
{
clear();
}

typedef typename Node_Iterator iterator;

Set(const Set &s)
{
_size = 0;
_root = NULL;
for(iterator it = s.begin(); it != s.end(); it++)
{
insert(*it);
}
}

Set& operator =(const Set &s)
{
if(&s == this) return *this;

clear();
for(iterator it = s.begin(); it != s.end(); it++)
{
insert(*it);
}
return *this;
}

void clear()
{
if(_root)
{
delete _root;
_root = NULL;
_size = 0;
}
}

size_t size() const
{
return _size;
}

bool empty() const
{
return _size == 0;
}

mutable size_t _size;
mutable Node_Set *_root;
mutable Node_Set *startIterator;

T& insert(const T& t)
{
return insert_imp(t, _root, _size);
}

bool find(const T& t, T*& result)
{
return (find_imp(t, result, _root) != NULL);
}

bool remove(const T& t)
{
T *result;
Node_Set **nodeRemove = find_imp(t, result, _root);

if(nodeRemove == NULL) {
return false;
}

_size--;
remove_imp(*nodeRemove);
return true;
}

iterator begin() const

Here are some things that may help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. It's especially bad to put into a header file as in the current code.

Use your own namespace

Combined with the problem above, your use of the name Set is not good. It is very similar to std::set and is also not very descriptive of the data structure. Since it's a tree, maybe name it Tree?

Don't use leading underscores in names

Anything with a leading underscore is a reserved name in C++ (and in C). See this question for details.

Prefer using to typedef in templates

The current code includes this line

typedef typename Node_Iterator iterator;

However this doesn't compile on my machine (and shouldn't compile on yours) because a typedef can't be a template. Instead, we have using which was introduced for that purpose:

using iterator = Node_Iterator;

Separate interface from implementation

It makes the code somewhat longer for a code review, but it's often very useful to separate the interface from the implementation. In C++, this is usually done by putting the interface into separate .h files and the corresponding implementation into .cpp files, but things are a bit different for header-only templates such as this one. However, I'd still recommend having an interface section and an implementation section to better aid users (or reviewers) of the code see and understand the interface.

Use nullptr rather than NULL

Modern C++ uses nullptr rather than NULL. See this answer for why and how it's useful.

Prefer modern initializers for constructors

The constructor use the more modern initializer style rather than the old style you're currently using. Instead of this:

Set()
{
    _size = 0;
    _root = NULL;
}

You could use this:

Set() :
    _size{0}, _root{nullptr}, startIterator{nullptr}
{}

Don't abuse mutable

The purpose for the mutable keyword is to mark things that can change but are not visible to the outside interface. For examle, it might be reasonble to declare your startIterator as mutable but it certatinly is not reasonable to declare _size and _root mutable!

Don't expose class internals

The insert() member function returns a reference to the data just inserted. This is not a good idea, because it then allows for internal data to be altered outside the class. Consider:

Set set;
int &foo = set.insert(0);
set.insert(1);
set.insert(2);
foo = 99;

Now the tree contains 1, 2 and 99.

Simplify node deletion

The code for remove_imp is much more complex than it needs to be.

static void remove_imp(Node_Set *&root)
{
    if(root == nullptr) {
        return;
    }

    if(root->_left == nullptr) {
        if (root->_right == nullptr) {
            delete root;
            root = nullptr;
        } else {
            Node_Set *rightNode = root->_right;
            root->_right = nullptr;
            delete root;
            root = rightNode;
        }
    } else {
        if (root->_right == nullptr) {
            Node_Set *leftNode = root->_left;
            root->_left = nullptr;
            delete root;
            root = leftNode;
        } else {
            Node_Set **left = &root->_right;
            while ((*left)->_left) {
                left = &(*left)->_left;
            }
            root->_value = (*left)->_value;
            remove_imp(*left);
        }
    }
}

StackExchange Code Review Q#161379, answer score: 4