Coding And Binary Tree implementation C++

Question

When searching for information about the Binary Tree, the code on people's blogs are complicated, so here I'm trying to code a very simple Binary Tree.

Am I missing anything? Is there a better way I could be implementing the BinTree::Remove?

#ifndef _BINTREE_H__
#define _BINTREE_H__
using namespace std;

class BinTree{
private:
    struct tree_node 
    {
        tree_node* left;
        tree_node* right;
        int data;
    };
    tree_node* root;
public:
    BinTree()
    {
        root = NULL; //Don't forget The constructor!It's Gonna kill the code
    }
    void Insert(int);
    //int nodes();
    bool IsEmpty(){ return root == NULL; }
    void print_Preorder();
    void Preorder(tree_node *);
    bool Search(int);
    void Remove(int);
};

void BinTree::Insert(int d){
    tree_node * t = new tree_node;
    tree_node * parent = NULL;
    t->data = d;
    t->left = NULL;
    t->right = NULL;

    if (IsEmpty()){
        root = t;
    }

    else{
        tree_node * curr;
        curr = root;
        while (curr){
            parent = curr;  
            if (t->data > curr->data) curr = curr->right;
            else curr = curr->left;
        }
        if (parent->data > t->data)
            parent->left = t;
        else
            parent->right = t;
    }
}

void BinTree::print_Preorder()
{
    Preorder(root);
}

void BinTree::Preorder(tree_node* p)
{
    if (p != NULL)
    {

        cout << " " << p->data << " ";
        if (p->left) Preorder(p->left);
        if (p->right) Preorder(p->right);
    }
    else return;
}


bool BinTree::Search(int d)
{
    bool found = false;
    if (IsEmpty())
    {
        cout << " This Tree is empty! " << endl;
        return false;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    parent = (tree_node*)NULL;
    while (curr != NULL)
    {
        if (curr->data == d)
        {
            found = true;
            break;
        }
        else
        {
            parent = curr;
            if (d>curr->data) curr = curr->right;
            else curr = curr->left;
        }
    }
    if (!found)
    {
        cout << " Data not found! " << endl;
    }
    else
    {
        cout << " Data found! " << endl;
    }

    return found;
}



void BinTree::Remove(int d)
{
    bool found = false;
    if (IsEmpty())
    {
        cout << " This Tree is empty! " << endl;
        return;
    }
    tree_node* curr;
    tree_node* parent;
    curr = root;
    parent = NULL;
    while (curr != NULL)
    {
        if (curr->data == d)
        {
            found = true;
            break;
        }
        else
        {
            parent = curr;
            if (d>curr->data) curr = curr->right;//l
            else curr = curr->left;
        }
    }
    if (!found)
    {
        cout << " Data not found! " << endl;
        return;
    }

    // Node with single child
    if ((curr->left == NULL && curr->right != NULL) || (curr->left != NULL
        && curr->right == NULL))
    {
        if (curr->left == NULL && curr->right != NULL)
        {
            if (parent->left == curr)
            {
                parent->left = curr->right;
                delete curr;
            }
            else
            {
                parent->right = curr->right;
                delete curr;
            }
        }
        else // left child present, no right child
        {
            if (parent->left == curr)
            {
                parent->left = curr->left;
                delete curr;
            }
            else
            {
                parent->right = curr->left;
                delete curr;
            }
        }
        return;
    }

    //We're looking at a leaf node
    if (curr->left == NULL && curr->right == NULL)
    {
        if (parent == NULL)
        {
            delete curr;

        }
        else
        if (parent->left == curr) parent->left = NULL;
        else parent->right = NULL;
        delete curr;
        return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != NULL && curr->right != NULL)
    {
        tree_node* chkr;
        chkr = curr->right;
        if ((chkr->left == NULL) && (chkr->right == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if ((curr->right)->left != NULL)
            {
                tree_node* lcurr;
                tree_node* lcurrp;
                lcurrp = curr->right;
                lcurr = (curr->right)->left;
                while (lcurr->left != NULL)
                {
                    lcurrp = lcurr;
                    lcurr = lcurr->left;
                }
                curr->data = lcurr->data;
                delete lcurr;
                lcurrp->left = NULL;
            }
            else
            {
                tree_node* tmp;
                tmp = curr->right;
                curr->data = tmp->data;
                curr->right = tmp->right;
                delete tmp;
            }

        }
        return;
    }

}
#endif

Answer 1

I assume you can use C++11, otherwise some of the points don't apply.

1. Don't put using namespace std; into a header, because everyone using your tree now also has the whole standard library in their namespace.

2. Put the public parts above the private parts. People are only interested in what they can actually use, not the implementation details.

3. Preorder should be private since it cannot be used in a meaningful way anyways.

4. Don't use NULL, use nullptr instead. NULL is just a macro for 0 (in theory it could be something else, but in practice it never is). Nonsensical things like int i = NULL; and int *p; p + NULL; compile even though they are clearly errors. nullptr doesn't have that issue.

5. Prefer initializing in the class directly instead of writing a constructor.

   class BinTree{
       tree_node *root = nullptr;
   }
   

   That way you can also leave out the constructor.

6. I dislike the name Search. The return value tells me if it searched or not? I would prefer contains so that the return value fits to the name.

7. Your BinTree leaks memory. It creates tree_nodes with new but doesn't delete them unless you manually call Remove for every single item. You have 2 options here: Insert a destructor that deletes all the nodes or just make root, right and left unique_ptrs, which will delete the nodes automatically. If you go the unique_ptr route you will have to change the implementation code a bit, because you cannot copy a unique_ptr (then it wouldn't be unique anymore) and instead std::move or std::swap them.

8. Your BinTree can be copied but the copy does the wrong thing. Instead of a copy I get 2 trees using the same nodes (because it just makes a copy of the root pointer). If I change one tree the other also changes. Instead you should write your own copy constructor that deep-copies the nodes. Same goes for the assignment operator. Also your BinTree would benefit from moving, so you should add a move-constructor and move-assignment, too.

9. Search prints stuff. As a user of your class I don't want that. Or at least let me specify an std::ostream where you should print it to.

10. Search should be a const function. Right now I cannot search for a value in a const BinTree tree;, but I should be able to.

11. In Search you keep the parent, but it is not used for anything. You could simplify that function to something like this:

    bool BinTree::Search(int d) const
    {
        const tree_node* curr = root;
        while (curr != nullptr)
        {
            if (curr->data == d)
                return true;
            if (d > curr->data)
                curr = curr->right;
            else
                curr = curr->left;
            //shorter, but lacks in readability:
            // curr = d > curr->data ? curr->right : curr->left;
        }
        return false;
    }        
    

12. Your BinTree is not balanced. If I insert numbers from 1 to 1000 I effectively get an inefficient linked list.

13. Remove is indeed a bit tricky. I would just replace the deleted node with the left node and insert the right node into the left node.

14. You could trivially replace int with T and put template <class T> above your tree to make it not only work with ints, but with any data type. In that case you should make 2 versions of functions that now take an int: One that takes a const T & and one that takes a T && that is then perfect forwarded.

There are good reasons why existing binary trees are so complicated. If you want lots of performance with lots of flexibility in lots of cases it costs you a lot of effort implementing the tree. Or you just use std::set and don't worry about it.