Binary Search Tree in c++ used to count words in a text

Question

I just created a BinarySeachTree class in c++ which is supposed to store words read from a txt and the number of occurances of those words and i would just like some feedback from you. I think it works correctly and i used valgrind to check if it creates any memory leaks (and it doesn't). I am just worried for some things like the two definitions of some functions, as i am not sure if it is a good practice the way i implemented it. There are a lot of comments in the code that i hope help make the code more understandable. Also i am required to do a technical report for my code and i am not sure how to go on about this, so any comments on this will be greatly appreciated.

Some questions I have are:

-Will the node class be inherited by the subclasses of the BinarySearchTree?

-Should the Node class have a destructor?

-I have to create the AVLTree class which inherits from BinarySearchTree and for the Insert function i will have to keep track of the height variable of Node. Would it be considered sloppy to just copy and paste the Insert function and just add some commands to keep track of height? If so, how could i go on about this?

Thank you for your time.

Header:

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include <string>
#include <iostream>
using namespace std;

class BinarySearchTree
{
    public:
        BinarySearchTree(); //constructor which creates an empty tree with a NULL root pointer
        ~BinarySearchTree(); //recursively deletes tree using postorder traversal by calling the Clear() method
        void Insert(string); //insert method is used to insert and also count occurences if while searching the tree we find that the given string already exists
        bool Search(string); //1st definition of search: this method will be used by main to search and display the contents of a node whose word is equal to the string
        bool Delete(string); //1st definition: deletes the node with the given string as its word, if it exists, by calling the 2nd Delete() definition and is only used by main
        void Preorder() {Preorder(root);} //For the traversal methods we use two definitions of each method, one that is called by main and one by the class,
        void Inorder() {Inorder(root);}   //as main does not have access to the root
        void Postorder() {Postorder(root);}

    protected:
        //Node class to be used only by BinarySearchTree and its children
        class Node
        {
            public:
                Node(string s) {word = s; occurences = 1;right = left = NULL;} //Node's constructor initialises node's values
                void print() {cout<<"Word: "<<word<<" Occurences: "<<occurences<<endl;}

                //Node's variables are set to public because Node will only be used inside BinarySearchTree and its chidlren
                int occurences;
                string word;
                Node* right;
                Node* left;
                int height; //this variable will be used only by BinarySearchTree's subclass AVLTree
        };
        Node* root;

        //methods only accessible by BinarySearchTree and its children
        bool Search(string, Node*&, Node*&); //2nd definition of search: this method will only be used by the class and its children to search for a node to be deleted and finds both the node and its parent
        void Preorder(Node*);
        void Inorder(Node*);
        void Postorder(Node*);
        void Clear(Node*);
        void FindMinOfRight(Node*, Node*&, Node*&); //this method will be used to delete a node that has two subtrees and it finds the minimum node (and its parent) of the right subtree of the node passed to it
        bool Delete(Node*, Node*);//2nd definition: first node is the child to be deleted and the second node is the parent

    private:

};

#endif // BINARYSEARCHTREE_H

Implementation:

#include "BinarySearchTree.h"

BinarySearchTree::BinarySearchTree()
{
    root = NULL;
}

BinarySearchTree::~BinarySearchTree()
{
    Clear(root);
}

void BinarySearchTree::FindMinOfRight(Node* n, Node* &m, Node* &pm)
{
    Node* prev_n = n;
    n = n->right;

    while(n->left)
    {
        prev_n = n;
        n = n->left;
    }

    m = n; //min
    pm = prev_n; //parent min
}

void BinarySearchTree::Clear(Node* n)
{
    if(!n)
        return;

    Clear(n->left);
    Clear(n->right);
    delete n;
}

void BinarySearchTree::Insert(string s)
{
    if(root) //on the first insertion the new node is the root
    {
        Node* n = root;
        Node* prev_n = NULL;

        while(n)
        {
            prev_n = n; //pointer variable to keep track of the parent node once n becomes NULL
            if(s > n->word) //if s is bigger than the current node's word we go to the right subtree
                n = n->right;
            else
            {
                if(s < n->word) //if s is smaller than current node's word we go to the left subtree
                    n = n->left;
                else //if s already exists in a node we just increment occurances by 1 and return
                {
                    n->occurences++;
                    return;
                }
            }
        }

        if(s > prev_n->word) //we create a new node in the place of the null pointer
        {
            prev_n->right = new Node(s);

            if(!prev_n->right) //we check if the memory allocation succeded
                cout<<"Memory allocation failed"<<endl;
        }
        else
        {
            prev_n->left = new Node(s);

            if(!prev_n->left)
                cout<<"Memory allocation failed"<<endl;
        }

    }
    else
    {
        root = new Node(s);

        if(!root)
            cout<<"Memory allocation failed"<<endl;
    }
}

bool BinarySearchTree::Search(string s)
{
    Node* n = root;

    while(n)
    {
        if(s > n->word) //if s is bigger than the node's word we search the right subtree of the node
            n = n->right;
        else
        {
            if(s < n->word) //if s is smaller than the node's word we search the left subtree of the node
                n = n->left;
            else //else the search was succesful
            {
                cout<<"Word: "<<n->word<<" Occurences: "<<n->occurences<<endl;
                return true;
            }
        }
    }
    //if we find a null pointer that means that we have reached a leaf of the tree and that s is not in it
    return false;
}

bool BinarySearchTree::Search(string s, Node* &c, Node* &p)
{
    Node* n = root;
    Node* prev_n = NULL;

    while(n)
    {
        if(s > n->word)
        {
            prev_n = n;
            n = n->right;
        }
        else
        {
            if(s < n->word)
            {
                prev_n = n;
                n = n->left;
            }
            else
            {
                c = n; //we use identical code to the 1st definition of search with the exception that instead of printing the node's content we store the node's and the node's parent's adress in the parameters
                p = prev_n;
                return true;
            }
         }
     }

     return false;
}

bool BinarySearchTree::Delete(string s)
{
    Node* c = NULL;
    Node* p = NULL;

    if(!(Search(s, c, p)))
        return false;

    return Delete(c, p);
}

bool BinarySearchTree::Delete(Node* c, Node* p)
{

    bool flag = false; //we use this flag to determine whether the node to be deleted is the right(true) or the left(false) child of its parent
        if(p && p->right == c)
            flag = true;

    //case 1: node to be deleted is a leaf
    if(!c->right && !c->left)
    {
        if(p) //if there is no parent we are deleting the root
        {
            if(flag)  //we set the pointer of the parent (left or right) that points to the node to be deleted to NULL then we delete the node
                p->right = NULL;
            else
                p->left = NULL;

            delete c;
        }
        else
        {
            delete root;
            root = NULL;
        }

        return true;
    }

    //case 2: node to be deleted has only one subtree
    if(c->right && !c->left)
    {
        if(p) //again we check to see if the node to be deleted is the root
        {
            if(flag)  //we check if the node to be deleted is the right or the left child of its parent so we can bypass it and delete it
                p->right = c->right;
            else
                p->left = c->right;

            delete c;
        }
        else
        {
            Node* temp = root->right;
            delete root;
            root = temp;
        }

        return true;
    }

    if(!c->right && c->left)
    {
        if(p)
        {
            if(flag)
                p->right = c->left;
            else
                p->left = c->left;

            delete c;
        }
        else
        {
            Node* temp = root->left;
            delete root;
            root = temp;
        }

        return true;
    }

    //case 3: node to be deleted has two subtrees
    Node* min_right;
    Node* pmin_right;
    Node* temp;

    if(p)
    {
        FindMinOfRight(c, min_right, pmin_right);
        temp = new Node(min_right->word);  //we store the contents of the min_right node that will take the place of the node to be deleted in a temp node
        temp->occurences = min_right->occurences;

        Delete(min_right, pmin_right); //we first delete the min_right node because there is a chance the node to be deleted and the parent of the min_right are the same node
                                       // this way we make sure the every node's chidlren will be correct
                                       //also this call of Delete() will fall one one of the first two cases as min_right will either be a leaf or have a right subtree

        temp->right = c->right; //then we assign to the temp node the children of the node to be deleted (as they should be after min_right is deleted)
        temp->left = c->left;

        delete c;

      if(flag) //finally we replace the node to be deleted with the min_right node
            p->right = temp;
        else
            p->left = temp;

        return true;
    }
    else //in this case we want to delete the root so we work as we did above with the exception that the root has no parent
    {
        FindMinOfRight(root, min_right, pmin_right);
        temp = new Node(min_right->word);
        temp->occurences = min_right->occurences;

        Delete(min_right, pmin_right);

        temp->right = root->right;
        temp->left = root->left;

        delete root;
        root = temp;

        return true;
    }

    return false; //in case something goes wrong
}

void BinarySearchTree::Preorder(Node* n)
{
    if(!n)
        return;

    n->print();
    Preorder(n->left);
    Preorder(n->right);
}

void BinarySearchTree::Inorder(Node* n)
{
    if(!n)
        return;

    Inorder(n->left);
    n->print();
    Inorder(n->right);
}

void BinarySearchTree::Postorder(Node* n)
{
    if(!n)
        return;

    Postorder(n->left);
    Postorder(n->right);
    n->print();
}

Answer 1

Overview

One major issue.
You take ownership of a pointer but don't implement the rule of three.

A series issue is that the code is not const correct. If a method does not modify the state of the object then it should be marked const. It is quite common for parameters to be passed as const reference in C++. If that is the case then you can only call const methods (since you don't have any then you can't call any).

An issue is that you pass parameters by value. This forces them to be copied. Most of the time you should pass by const reference to prevent a copy.

Code Review

That's relatively common guard name!

#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

I would try an make it more unique, possibly by including the namesapce you put your code into the name of the guard.

---

You did not put your code in a namespace.
Should probably do that BinarySearchTree seems like having. ahigh probability of being defined by multiple people.

---

Never do this.

using namespace std;

Its terrible when people do this in a source file. But doing it in a header file can actually break other peoples code. Stuff like this will get you banned from contributing.

1. Never ever ever do it in a header file.
   It not only affects your code but any code that includes your header.
2. Preferably don't even do it your own source files.
3. Limitted using std::<something>;
   This can an be acceptable but prefer to limit its scope. But even this is not worth it.
4. The reason that the "Standard" namespace is called "std" is so that it is not a burden to use the prefix on objects and types. std::vector<int> is that so hard?

Read details about the issues here: Why is “using namespace std;” considered bad practice?

---

Your comments are horrible:

    public:
        BinarySearchTree(); //constructor which creates an empty tree with a NULL root pointer
        ~BinarySearchTree(); //recursively deletes tree using postorder traversal by calling the Clear() method
        void Insert(string); //insert method is used to insert and also count occurences if while searching the tree we find that the given string already exists
        bool Search(string); //1st definition of search: this method will be used by main to search and display the contents of a node whose word is equal to the string
        bool Delete(string); //1st definition: deletes the node with the given string as its word, if it exists, by calling the 2nd Delete() definition and is only used by main
        void Preorder() {Preorder(root);} //For the traversal methods we use two definitions of each method, one that is called by main and one by the class,
        void Inorder() {Inorder(root);}   //as main does not have access to the root

Don't write this type of comment. A comment that only describes the code is worse than useless. This actually costs effort to maintain as you must make sure that the comments and code stay in sink over time (comment rot in old code bases is a real thing and is a problem).

Write comments to explain WHY. The code explains HOW. Use self documenting code (like you have). Using good variable and method names is the key to writing good maintainable code.

How not to writing bad comments should definitely be a course at university these days.

---

You are passing parameters by value:

        void Insert(string);
        bool Search(string);
        bool Delete(string);

This forces a copy of the object from the call location and creates a new value (as the parameter) in the function. What you should be doing is passing by const reference to prevent a copy.

        void Insert(string const&);
        bool Search(string const&);
        bool Delete(string const&);

If you want to get advanced. The insert operator you can pass by r-value reference and allow the Node to re-use the pointer you created externally rather than make a copy when creating the node object.

        void Insert(string&&);

---

OK. SO you have different methods to iterate over the tree.

        void Preorder()  {Preorder(root);}
        void Inorder()   {Inorder(root);}
        void Postorder() {Postorder(root);}

But I don't understand how that helps me. I can't do anything by simply iterating over the tree. So what does this give me? Let me take a look at their implementation.

Ahhh. They all call print(). So you can print out the tree in different orders. Sure that is fine. But name the functions mroe appropriately.

        void PreorderPrint()  {PreorderPrint(root);}
        void InorderPrint()   {InorderPrint(root);}
        void PostorderPrint() {PostorderPrint(root);}

---

Lets look at the traversal of the tree for a second.

Rather than simply supporting printing why not allow the user to iterate over the tree and perform some action. You could pass a functor (or lambda) as a parameter that then gets executed on each value in the tree.

Or you could implement the visitor pattern.

---

Personally I think this is fine.

        Node* root;

You are explicitly making the BinarySearchTree the owner of the tree. But with that comes some extra responsibility that you need to take on (more of that in a second). Alternatively you can use a smart pointer to manage the memory:

        std::unique_ptr<Node>  root;

This delegates the ownership of the memory to unique_ptr to manage correctly (which it does).

So what is the problem with your code?
Your code ownes the pointer root BUT you don't implement the rule of three (or five). This means your code is fundamentally broken.

{
    BinarySearchTree   t;
    t.Insert("Loki");

    BinarySearchTree   t2(t);  // Shallow copy of the tree created.
                               // Both t and t2 have the same value of root.
                               // i.e. both point at the same tree.
}
// Both t and t2 go out of scope.
// t2 destroyed and calls clear on tree (OK).
// t1 destroyed and calls clear on tree (this is an issue as this tree
//                                       was already deleted......)

So if you want to make this a pointer you must implement the rule of three (look it up, it is a very common idiom in C++).

The easiest way to solve this is simply to use std::unique_ptr for root and then the left and right pointers in Node. But the rest of this review assumes you want to keep ownership and implement the extra methods to solve this.

---

If a method does not modify the tree then it should be marked const.

 // I think all these functions should be marked const.
        bool Search(string, Node*&, Node*&);
        void Preorder(Node*);
        void Inorder(Node*);
        void Postorder(Node*);
        void FindMinOfRight(Node*, Node*&, Node*&);

---

You are using "OUT" parameters. This is pretty horrible to read. It is easy to return a value and it makes it obvious what the function does. You can return multiple values by creating a simple class or using a wrapper like std::pair or std::tuple.

        bool Search(string, Node*&, Node*&);
        void FindMinOfRight(Node*, Node*&, Node*&);

I think you will find it will also make some of your code simpler.

---

Not sure what this private section is for.

    private:

Just remove it.

---

The value NULL is no longer considered good practice. This is because it is a macro and is usually a number (not sure on the exact definition). But as a result it can be assigned to things it should not be able to assigned to and thus hide errors.

In modern C++ we use nullptr to represent the value 'null'. It has a specific type std::nullptr_t. This type is automatically convertible to another pointer type but will not auto convert into a numeric type and thus can not accidentally be passed to methods that take int as parameter.

---

Prefer to use an initializer liest.

BinarySearchTree::BinarySearchTree()
{
    root = NULL;
}

I would write like this:

BinarySearchTree::BinarySearchTree()
    : root(nullptr)
{}

In this situation it does not make any difference (as there are no constructors called). But in a lot of situations this can cause a lot of extra work. So it is best to use the initializer list and be consistent about its use to prevent accidentally incurring extra cost.

If we look at the node constructor:

Node(string s)
{
    word = s;
    occurences = 1;
    right = left = NULL;
} //Node's constructor initialises node's values

Example of a bad comment above!

But if we look at what is actually happening here. The member word is default constructed, then in the body you are calling the assignment operator to update word with the value of s. Effectively your code is equivalent to:

Node(string s)
    : word()        // Note word is defaulted constructed here.
{
    word = s;       // Now we call the assignment operator.
    // STUFF
}

The better way to do it is using the initializer list:

Node(string s)
    : occurences(1)
    , word(s)
    , right(nullptr)
    , left(nullptr)
    , height(0)
{}

---

Your function names are so good.
Why are your variable names so bad!!!!!

void BinarySearchTree::FindMinOfRight(Node* n, Node* &m, Node* &pm)
{
   // STUFF

    m = n; //min               // You could have saved yourself a comment
                               // and made the code more readable by nameing
                               // these two variable "better"!!!!
    pm = prev_n; //parent min
}

---

This could be better:

void BinarySearchTree::FindMinOfRight(Node* n, Node* &m, Node* &pm)

You don't need to return two values. You need to return a reference to the pointer that needs to be changed.

Node*& BinarySearchTree::FindMinOfRight(Node*& n)
{
    auto nRef = std::ref(n);

    while(nRef->left) {
        nRef = nRef->left;
    }
    return *nRef;
}

// See below for usage:

---

Please always put in the braces.

    if(!n)
        return;

I would write this:

    if(!n) {
        return;
    }

The number of time I have fixed problems because people forgot that adding an indent line is not enough to make it executed by the loop the conditional etc...

---

OK this is fine:

    Clear(n->left);
    Clear(n->right);
    delete n;

I disagree with @ALX23z that this is likely to cause a SO. Remember that most implementations are going to use std::unique_ptr<Node>. This results in exactly the same behavior.

BUT. If you do want to do this optimally its not that hard to convert this from a recursive call into a serial call.

 void Clear(Node* n)
 {
     if (!node) {
         return;
     }

     // We are going to flatten the tree into a list.
     // by moving all the right nodes to the botomLeft as we go.
     // So:
     //     bottomLeft:  represents the current bottom left of our list.
     //     n:           The node we are about to delete.
     //                  If n has a right node then move it to the bottomLeft
     //                  and move the `bottomLeft` to a new point.
     //                  Now we can delete `n`
     //
     // We will eventually reach the end.
     // This is a simple serial deltion of the tree using a loop.

     Node* bottomLeft = n;
     while (bottomLeft->left) {
         bottomLeft = bottomLeft->left;
     }

     while (n) {
         bottomLeft->left = n->right;
         while (bottomLeft->left) {
             bottomLeft = bottomLeft->left;
         }
         Node* next = n->left;
         delete n;
         n = next;
     }
}

---

You make this way to hard:

void BinarySearchTree::Insert(string s)

I would re-write like this:

void BinarySearchTree::Insert(string const& s)
    root = Insert(s, root);
}

Node* BinarySearchTree::Insert(string const& s, Node* n)
    if (n == nullptr) {
        return new Node(s);
    }
    if (s < n.value) {
        n->left = Insert(s, n->left);
    }
    else if (n.value < s) {
        n->right = Insert(s, n->right);
    }
    else {
        n->occurences++;
    }
    return n;
}

---

Easy mistake:

            prev_n->left = new Node(s);

        // This will NEVER be called.    
            if(!prev_n->left)
                cout<<"Memory allocation failed"<<endl;

If new fails (i.e. it can't allocate anything) then it throws an exception. It will never return nullptr.

---

Nothing wrong here (apart from unholy bad comments).

bool BinarySearchTree::Search(string s)
{
    Node* n = root;

    while(n)
    {
        if(s > n->word)
            n = n->right;
        else
        {
            if(s < n->word)
                n = n->left;
            else
            {
                cout<<"Word: "<<n->word<<" Occurences: "<<n->occurences<<endl;
                return true;
            }
        }
    }
    return false;
}

But I would simply write those if else blocks like they were all part of the same test.

bool BinarySearchTree::Search(string s)
{
    Node* n = root;

    while(n)
    {
        if(s > n->word) {
            n = n->right;
        }
        else if(s < n->word) {
            n = n->left;
        }
        else
        {
            cout<<"Word: "<<n->word<<" Occurences: "<<n->occurences<<endl;
            return true;
        }
    }
    return false;
}

---

Man you make this complicated:

bool BinarySearchTree::Delete(string s)

Easier:

bool BinarySearchTree::Delete(string const& s) {
    bool result = false;
    root = Delete(s, root, result);
    return result;
}

Node* BinarySearchTree::Delete(string const& s, Node* n, bool& result) {
    if (n == nullptr) {
        return nullptr;
    }

    Node* retValue = n;

    if (s < n.value) {
        n->left = Delete(s, n->left, result);
    }
    else if (n.value < s) {
        n->right = Delete(s, n->right, result);
    }
    else {
         // Found the node we want to delete:
         result = true;

         if (node->left == nullptr && node->right == nullptr) {
             retValue = nullptr
         }
         else if (node->left == nulltr) {
             retValue = node->right;
         }
         else if (node->right == nullptr) {
             retValue = node->left;
         }
         else {
            Node*&   nodeToReplaceThis = FindMinOfRight(n->right);
            n->value = nodeToReplaceThis->value;
        
            n = nodeToReplaceThis;
            nodeToReplaceThis = n->right;  // Remember this is a reference
                                           // So we are effectively changing
                                           // what the parent node points at.

            // Note: No change in retValue.
            //       and n has been moved to the node we want to delete.
         }
         delete n;
    }
    return retValue;
}

Answer 2

The binary search tree you have here is a very naive implementation and has fundamental flaws. And this binary search tree implementation is not an AVLTree.

1) It lacks tree balancing scheme - meaning there is no promise that search will take O(log(n)).

Imagine you put strings into the tree in ascending order. This implementation will always go to the rightmost and put it there. Meaning, it will take O(n^2) time just to make it. And all searches will require O(n) time.

2) It suffers from quite likely stackoverflow on destruction. You have recursive clear functions. Imagine the tree isn't balanced as in example from (1) - then you'll have n stacked calls to Clear() which will overflow the callstack.

3) It lack standart container interface. E.g., iterators and begin() and end() methods as well as efficient size() function.

About your questions.

Should the Node class have a destructor?

Due to stackoverflow issues usually they don't bother implementing destructors for nodes - as the tree requires very specialized destructor. Unless you plan to use the nodes elsewhere (which I don't advice). In which case, you could use std::unique_ptr<Node> for pointers instead of working with raw pointers Node* as these automatically handle most of the basic problems.

Will the node class be inherited by the subclasses of the BinarySearchTree?

Not sure what exactly you mean. Since it is defined under protected then all classes that inherit from BinarySearchTree will have access to it (lest there is some private inheritance in the middle).

Generally, I don't think that there is any real point in defining simple classes under private or protected. Just make it public.

I have to create the AVLTree class which inherits from BinarySearchTree and for the Insert function i will have to keep track of the height variable of Node. Would it be considered sloppy to just copy and paste the Insert function and just add some commands to keep track of height? If so, how could i go on about this?

You really need such a design? I'd advise to write AVLTree directly without the BinarySearchTree as base class.

Generally, I don't think there is much purpose in implementing a binary search tree other than for exercising since there are well maintained implementations in STL and some other libraries.