Binary search tree implementation with Rule of Three

Question

I am 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 realise 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 <iostream>

template <class T>
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<class T>
Tree<T>::Tree():root(NULL){}

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

template<class T>
void Tree<T>::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<class T>
const Tree<T>& Tree<T>::operator=(const Tree& rhs){
    if(this!=&rhs){
        copyTree(this->root,rhs.root);
    }
    return *this;
}

template<class T>
Tree<T>::~Tree(){
    delete root;
}

template<class T>
void Tree<T>::insert(T _data){
    if(root==NULL)
        root = new TreeNode(_data);
    else{
        insertHelper(_data, root);
    }
}

template<class T>
void Tree<T>::insertHelper(T data, TreeNode *leaf){
    if(data < leaf->data){
        if(leaf->left == NULL){
            TreeNode *newNode = new TreeNode(data);
            leaf->left = newNode;
        }else
            insertHelper(data,leaf->left);
    }else if(data > leaf->data){
        if(leaf->right==NULL){
            TreeNode *newNode = new TreeNode(data);
            leaf->right = newNode;
            return;
        }
        insertHelper(data,leaf->right);
    }else{
        std::cout << "The data already exist" << std::endl;
    }
}

template<class T>
void Tree<T>::Delete(T _data){
    if(root==NULL){
        std::cout <<"The Tree is empty\n";
        return;
    }
    DeleteHelper(_data,root);
}
template<class T>
void Tree<T>::DeleteHelper(T _data,TreeNode* &rootRef){
    if(rootRef==NULL)
        return;
    if(_data==rootRef->data)
        DeleteNode(rootRef);
    else if(_data < rootRef->data)
        DeleteHelper(_data,rootRef->left);
    else if(_data > rootRef->data)
        DeleteHelper(_data,rootRef->right);
}
template<class T>
void Tree<T>::DeleteNode(TreeNode* &rootRef){
    // The current node has no children
    TreeNode* temp = rootRef;
    if(rootRef->left==NULL && rootRef->right==NULL)
        rootRef = NULL;
    else if(rootRef->left==NULL && rootRef->right!=NULL)
        rootRef = rootRef->right;
    else if(rootRef->left!=NULL && rootRef->right==NULL)
        rootRef = rootRef->left;
    else{ //current node has two childreen
        //find the smallest element in the right subtree
        TreeNode* parent = rootRef;
        temp = rootRef->right;
        temp = findSmallest(temp,parent);
        rootRef->data = temp->data;
        if(parent==rootRef)
            parent->right = temp->right;
        else
            parent->left = temp->left;
    }
    delete temp;
}

template<class T>
typename Tree<T>::TreeNode* Tree<T>::findSmallest(TreeNode *root, TreeNode *&parent){
    if(root->left==nullptr)
        return root;
    return findSmallest(root->left,root);
}
template<class T>
void Tree<T>::print()const{
    if(root==NULL)
        std::cout << "The Tree has no element" << std::endl;
    else
        printHelper(root);
}

template<class T>
void Tree<T>::printHelper(TreeNode *root)const{
     if(root==NULL)
         return;
    printHelper(root->left);
    std::cout << root->data << " " << std::endl;
    printHelper(root->right);
}

template<class T>
bool Tree<T>::searchElement(T _data){
    return searchElementHelper(_data,root);
}

template<class T>
bool Tree<T>::searchElementHelper(T _data,TreeNode *rootRef){
    if(rootRef==NULL)
        return false;
    if(_data==rootRef->data)
        return true;
    if(_data < rootRef->data)
        return searchElementHelper(_data,rootRef->left);
    if(_data > rootRef->data)
        return searchElementHelper(_data,rootRef->right);
    return false;
}
int main(int argc, const char * argv[]) {
    Tree<int> tree;
    tree.insert(12);
    tree.insert(10);
    tree.insert(19);
    tree.insert(11);
    tree.insert(16);
    tree.insert(13);
    tree.insert(15);
    tree.insert(14);
    tree.Delete(16);
    if(tree.searchElement(16))
        std::cout << "Found" << std::endl;
    else
        std::cout << "NOT Found" << std::endl;
    tree.print();
    Tree<int> tree2 = tree;
    std::cout<<"The elements of Tree 2: \n";
    tree2.print();

    Tree<int> tree3;
    tree3 = tree2;
    std::cout <<"The elements of Tree 3: \n";
    tree3.print();
    return 0;
}

Have you deliberately decided not to use c++11 features? If so, why did you tag it with c++11? — MikeMB, Jul 28 at 22:24
@MikeMB, thanks for your responds. Firstly, honestly, I want to use c++11 features but haven't tried it. I will edit my tag post. For the destructor, I just not sure about it that is why i commented it. — bohr, Jul 28 at 22:29
Unfortunately, I don't have time for a real review at the moment. But I'd recommend reading about smart pointers (especially std::unique_ptr) and applying them to your class. At a glance, it seems as if you have some memory leaks that could easily be prevented that way (as a first order of approximation: Don't use new in c++14 and beyond, but make_unique and make_shared instead). Also since c++11, the "Rule of 3/4/5/0" concep has become pretty useless in my opinion. You e.g. often don't need a destructor anymore. — MikeMB, Jul 28 at 22:50
One remark: While implementing a binary tree with dynamic allocation of nodes is a good programming exercise, binary search data structures can be implemented in a much much more efficient manner by packing everything in an array / std::vector (instead of allocating each node independently). — BrunoLevy, Aug 2 at 10:38

Morwenn · Accepted Answer · 2015-07-29 18:05:44Z

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 hat 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 prform 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 coy a whole tree:
```
template<class T>
Tree<T>::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 encountr any return statement. That behviour 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 responsibiities between Tree and TreeNode. For example, here is how I would rewrite the contains method, letting TreeNode handle more things:

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

template<class T>
bool Tree<T>::TreeNode::contains(T value) const {
    if (value == data) {
        return true;
    }
    if (value < data) {
        return left && left->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.

Thank you so much @Morwenn, I really appreciate your feedback. Indeed, there are some bugs in my node removal algorithm, and now it works like charm. However, I have a question about defining a function as a const function. Why it is necessary to define for instance in my implementation searchElementHelper as constant? well, I understand about it gives clearer information which one will modify and which one not. But can you give more specific example, like in a real project? Thanks — bohr, Jul 29 at 20:02
@user2997327 Making const methods allows you to use them on a const Tree<int>. For example, if a function is a declared as void foobar(const Tree<int>& tree), it can still call tree.searchElement while it wouldn't be possible if searchElement wasn't marked as const. — Morwenn, Jul 29 at 20:18

asked	1 month ago
viewed	71 times
active	1 month ago

current community

your communities

more stack exchange communities

Binary search tree implementation with Rule of Three

1 Answer 1

Your Answer

Not the answer you're looking for? Browse other questions tagged c++ tree or ask your own question.

Hot Network Questions

current community

your communities

more stack exchange communities

Binary search tree implementation with Rule of Three

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c++ tree or ask your own question.

Related

Hot Network Questions