Binary search tree implementation with Rule of Three

I started to code in C++ and tried to implement a simple BST data structure. Since at the moment I am learning about the Rule of Three, I tried to implement it in my code. Yet, I realize that my code might be far from efficient. I also doubt whether I've made a right destructor or not.

What are the best practices to use the Rule of Three, especially in this particular implementation (BST)? I would really open for any comments and suggestions.

```
#include

template
class Tree{
private:
struct TreeNode{
T data;
TreeNode *left;
TreeNode *right;

TreeNode(T val):data(val),left(NULL),right(NULL){}
//~TreeNode(){
// delete left;
// delete right;
//}
};

TreeNode *root;
void printHelper(TreeNode *)const;
void insertHelper(T data, TreeNode *leaf);
void DeleteHelper(T data, TreeNode* &);
void DeleteNode(TreeNode* &);
bool searchElementHelper(T key, TreeNode *leaf);
void copyTree(TreeNode &thisRoot, TreeNode rhsRoot);
TreeNode findSmallest(TreeNode ,TreeNode *&);
public:
Tree();
~Tree();
Tree(const Tree& rhs);
const Tree& operator=(const Tree& rhs);
void insert(T);
void Delete(T);
void print()const;
bool searchElement(T _data);
};

template
Tree::Tree():root(NULL){}

template
Tree::Tree(const Tree& rhs){
if(rhs.root==NULL)
root=NULL;
else
copyTree(root,rhs.root);
}

template
void Tree::copyTree(TreeNode &thisRoot,TreeNode rhsRoot){
if(rhsRoot==NULL)
thisRoot=NULL;
else{
thisRoot = new TreeNode(rhsRoot->data);
copyTree(thisRoot->left,rhsRoot->left);
copyTree(thisRoot->right,rhsRoot->right);
}
}

template
const Tree& Tree::operator=(const Tree& rhs){
if(this!=&rhs){
copyTree(this->root,rhs.root);
}
return *this;
}

template
Tree::~Tree(){
delete root;
}

template
void Tree::insert(T _data){
if(root==NULL)
root = new TreeNode(

I have a couple of remarks. Generally speaking, I will try to add tags such as c++11 or c++14 before each so that you know which version you need for which improvement. If there isn't a tag, assume that it works with C++03:

-
c++11 Use nullptr instead of NULL to represent null pointers. It is safer since it avoids some problems: for example, if a function foo has an int overload and a char overload, foo(NULL) will pick the int overload while foo(nullptr) will pick the char overload, which is probaby what you would expect.

-
You have some bugs. For example, the fact that you wrote a destructor for TreeNode but commented it out clearly highlights that there is a problem in your code (for example, it leaks memory since you never delete it properly). And indeed there is a problem: if we uncomment it, it shows that the Delete function frees memory where it shouldn't. It means that you have a bug somewhere in your Delete algorithm. But where?

The answer is that when you perform delete temp; in DeleteNode, temp still refers to the old root and since you just assigned it one of its children, it also deletes the children while deleting the old root. Therefore, you need to assign nullptr to the old root's left and right fields before deleting it:

temp->right = nullptr;
temp->left = nullptr;
delete temp;

Now you can uncomment TreeNode's destructor and enjoy a correct code without memory leaks.

-
c++11 Consider adding a move constructor and a move assignment operator to your class. The cost of moving a tree is trivial compared to what it costs to copy a whole tree:

template
Tree::Tree(Tree&& other):
    root(other.root)
{
    other.root = nullptr;
}

See, all the move constructor does is acquire the memory managed by other and assign nullptr to other.root so that the memory does not get freed when other is destructed.

-
const-correctness is important in C++. When one of your methods does not modify a class, mark it const. Not only will it make it clear which functions modify the class and which ones do not, but it is also essential if you need to use these functions in a const context.

bool searchElementHelper(T key, TreeNode *leaf) const;
                                                ^^^^^

-
Use more spaces, for example, around the operators. As of right now, your code looks a bit like a big "block" and could use a bit more space to breath.

-
Also, be consistent when naming your functions. I know that you can't use delete as a method name since it's a keyword, but in this case look for a synonym such as remove or erase (the second one would be consistent with the names used in the standard library). Consistency is the key to usability and maintainability.

-
Speaking of consistency, it's good practice to always use curly braces with flow control statements, even if there is only one statement between the curly braces. Not only does it make it easier to add more statements later, but it also prevents stupid mistakes such as Apple's goto fail bug that can go unnoticed and wreak havoc in your program.

-
You don't need to return 0; at the end of main: the compiler will do it for you if it doesn't encounter any return statement. That behaviour is often used as a way to document that your main cannot return anything else than 0.

-
I would expect a searchElement method to return at least an iterator or a pointer of some kind to the searched element. To avoid confusion, a better name for the method you wrote would be contains.

-
You might want a better separation of responsibilities between Tree and TreeNode. For example, here is how I would rewrite the contains method, letting TreeNode handle more things:

template
bool Tree::contains(T value) const {
    if (root == nullptr) {
        return false;
    }
    return root->contains(value);
}

template
bool Tree::TreeNode::contains(T value) const {
    if (value == data) {
        return true;
    }
    if (value contains(value);
    }
    if (value > data) {
        return right && right->contains(value);
    }
    return false;
}

I find this code easier to reason about since, once in TreeNode::contains, it is clear that we will only deal with data, left and right and nothing else besides the function's parameters. It lessens the cognitive effort for the reader.

-
By the way, you could reduce redundancy in naming by renaming Tree::TreeNode into Tree::Node. Since it's an inner class, you already have the information that it is a Tree node from the enclosing class name.

StackExchange Code Review Q#98388, answer score: 4