Binary search tree in C++, and display, search and delete functions

Question

I feel ready to show you my work on creating BST in C++ using double linked list and 3 more functions for manipulating the tree. There is also one more function checking if the tree is real or not.

Declaring the Node:

#include <iostream>
#include <string>
#include <vector>
#include <fstream>


struct BstNode
{ //structuring a node
    std::string data;
    BstNode* left;
    BstNode* right;
    int frequ;
};

Node creator func:

BstNode* NewNodeCreator(std::string data)  //creating a new node, pointing left and right to null
{
    /*I make a pointer, pointing to a new space in memory. To allocate that memory I am using new operator, taking sizeof(BstNode) struct*/
    BstNode* newNode = new BstNode();

    newNode->data = data;
    newNode->left = newNode->right = NULL; // left and right poiners to NULL
    newNode->frequ = 1; //for first time in BST
    return newNode;
}

Opening the text file and read it's content ( a simple sentence ) :

std::vector<std::string> readFromTxt()
{ //extracting words for a text file
    std::ifstream book("text.txt"); //open and read txt file
    std::string word;
    std::vector<std::string> list;

    if (!book.is_open())
    {
        std::cout << "Unable to open file";
        system("pause");
        exit(1);
    }
    while (book >> word)
    {
        list.emplace_back(word); //store the words in a vector
    }
    return list;
}

Inserting the new node into the BST:

BstNode* InsertNode(BstNode* root, std::string data)
{ //inserting node and creating a binary tree
    if (root == NULL)
    {
        return NewNodeCreator(data);
    }
    if (data == root->data) // If the string already exists in BST, count+1 and return 
    {
        (root->frequ)++;
        return root;
    }
    else if (root->data > data)
    {
        root->left = InsertNode(root->left, data);
    }
    else
    {
        root->right = InsertNode(root->right, data);
    }
    return root;
}

Display the BST in preorder:

void InPreorder(BstNode* root) //function for ptinting the BST in pre-order
{
    if (root == NULL)
        return;
    // print data of node 
    std::cout << "<" << root->frequ << ">" << " " << root->data << "\n";

    //going to left node
    InPreorder(root->left);

    //going to right
    InPreorder(root->right);
}

Searching algorithm:

void Search(BstNode* root, std::string data) //serching through the BST for specific word
{
    if (root == NULL)
    {
        std::cout << "Not found\n";
        return;
    }

    else if (root->data == data)
    {
        std::cout << "Found\n";
    }
    else if (data < root->data)
    {
        std::cout << "Goind left\n";
        return Search(root->left, data);
    }
    else {
        std::cout << "Goind right\n";
        return Search(root->right, data);
    }
}

The delete function and simple func to find the smallest value in the right root:

BstNode* minValue(BstNode* root) //easy way to find the min value in the leftmost leaf
{
    BstNode* minData = root;

    while (minData->left != NULL)
    {
        minData = minData->left;
    }
    return minData;
}

BstNode* NodeDestructor(BstNode* root, std::string data) //deleting a node in BST
{
    if (root == NULL)
    {
        return root;
    }
    if (data < root->data)  // Searching in BST for the value
    {
        root->left = NodeDestructor(root->left, data);
    }
    else if (data > root->data)
    {
        root->right = NodeDestructor(root->right, data);
    }
    else //when the value is found
    {
        if (root->left == NULL && root->right == NULL) //for node with no child
        {
            delete root;
            root = NULL;
        }
        else if (root->left == NULL)//only one child
        {
            BstNode *temp = root->right;
            delete root;
            return temp;
        }
        else if (root->right == NULL)
        {
            BstNode *temp = root->left;
            delete root;
            return temp;
        }
        else //for node with two children
        {
            BstNode* minData = root->right;

            while (minData->left != NULL)
            {
                minData = minData->left;
            }
            return minData;

            BstNode *temp = minData;
            root->data = temp->data;
            root->right = NodeDestructor(root->right, temp->data);
        }
    }
    return root;
}

Here I test the BST:

bool isBST(BstNode* root, BstNode* left = NULL, BstNode* right = NULL)  //funciton for checking if the tree is properly created
{                                                                    // Base condition 
    if (root == NULL)
    {
        return true;
    }

    if (left != NULL and root->data < left->data)
    {
        return false;
    }

    if (right != NULL and root->data > right->data)
    {
        return false;
    }
    // check recursively for every node. 
    return isBST(root->left, left, root) and isBST(root->right, root, right);
}

And finally the main function:

int main()
{
    BstNode* root = NULL;
    int i, note, j;
    std::vector<std::string> test; //define a vector to store words from txt file
    test = readFromTxt();

    for (j = 0; j < test.size(); j++) //This loop is bulding the three passing english words
    {
        std::string str1 = test[j];

        root = InsertNode(root, str1);
    }

    if (isBST(root, NULL, NULL)) //calling BST check function
    {
        std::cout << "Is BST\n";
    }
    else
    {
        std::cout << "Not a BST\n";
    }


    InPreorder(root);
    Search(root, "in");
    NodeDestructor(root, "in");
    InPreorder(root);
    Search(root, "in");

    delete root;
    return 0;
}

I hope It's useful for programmers who are trying to implement a BST using C++. I'm open for critical comments.

Answer 1

Overview

Your biggest issue is encapsulation (there is none).

Start writing classes with methods.
Only allow the class methods to modify the internal members.

I would note that std::map has the same characteristics as a balanced binary search tree (this implies its implementation is a Red/Black tree).

I don't mention it in the code below. But when passing object you usally pass by const reference. This will avoid unneeded copies being created. You pass the strings around by value which cause a copy of the string to be created with each function call (that's expensive).

If you re-write to include all the above advice we can discuss the opportunities that come with using move semantics.

Code Review

Why is this a function?

BstNode* NewNodeCreator(std::string data)  //creating a new node, pointing left and right to null
{
    /*I make a pointer, pointing to a new space in memory. To allocate that memory I am using new operator, taking sizeof(BstNode) struct*/
    BstNode* newNode = new BstNode();

    newNode->data = data;
    newNode->left = newNode->right = NULL; // left and right poiners to NULL
    newNode->frequ = 1; //for first time in BST
    return newNode;
}

This should be the constructor of BstNode

There is a much simpler way to read a text file into a vector.

std::vector<std::string>   list;
...
while (book >> word)
{
    list.emplace_back(word); //store the words in a vector
}

I would write this as:

// Iterate over a stream and build a vector.
std::vector<std::string>   list(std::istream_iterator<std::string>(book),
                                std::istream_iterator());

I would avoid using exit().

if (!book.is_open())
{
    std::cout << "Unable to open file";
    system("pause");
    exit(1);
}

This is an unexpected (otherwise you would not exit). So throw an exception. You can catch exceptions in main and display an error message. By doing it this way your code to display error messages is in a single location and not spread around the code. This makes the error messages (or the way the application exits consistent across all errors).

if (!book.is_open()) {
    throw std::runtime_error("Unable to open file");
}

Another place where you have a function rather than a method:

BstNode* InsertNode(BstNode* root, std::string data);

The trouble here is that you call your insert like this

root = InsertNode(root, "Blob");

But there is nothing to stop a person modifying the variable root. What happens if they modify the tress pointed at by root so that it is no longer consistent with a BST?

What you should do is make root a private member of a class. The only way to modify root is to call the InsertNode() method. That way you know that your tree is always going to be a BST.

class BSTTree
{
    private:
        BSTNode*   root;

        void InsertNode(BSTNode* node, std::string data);
    public:
        BSTTree()
            : root(nullptr)
        {}
        void InsertNode(std::string data) {
            root = InsertNode(root, data);
        }
}

You are definitely going in the correct direction here. But you need to fix a couple of bugs here:

    else //for node with two children
    {
        BstNode* minData = root->right;

        while (minData->left != NULL)
        {
            minData = minData->left;
        }
        return minData;             // This return is wrong.

        BstNode *temp = minData;
        root->data = temp->data;
        root->right = NodeDestructor(root->right, temp->data);
    }

I think you want:

    else //for node with two children
    {
        BstNode* minData = minValue(root->right);

        root->data  = minData->data;
        root-> frequ= minData-> frequ;
        root->right = NodeDestructor(root->right, root->data);
    }