Binary Search Trees! Simple Class in C++

Here is a really basic binary tree class, it just includes the basics of creating, inserting, erasing, and returning size. In later posts I will talk about printing and traversals.

This class also uses the Node.h talked about in this earlier post. You’ll notice that I really like to use recursion, I think this is cleaner than looping.

#include <assert.h>
#include "Node.h"
using namespace std;

class Bst
{
    public:

        //constructor for when a head Node is provided and when it is not
        Bst() {
            root = nullptr;
        }

        Bst(Node *np) {
            root = np;
        }

        //destroy the tree, we need to go through and destroy each node
        ~Bst() {
            destroyTree(root);
        }

        //get the number of nodes in the tree
        int size() {
            return size(root);
        }

        //erase a value in the tree
        void erase(int item) {
            erase(item, root);
        }

        //insert a Node in the tree
        void insert(int item) {
            insert(item, root);
        }

    private:

        Node* root;

        //Go through each branch and recursively destroy all Nodes
        void destroyTree(Node*& n) {
            if (n != nullptr) {
                destroyTree(n->left);
                destroyTree(n->right);
                delete n;
            }
        }

        //For each Node return the number of left and right nodes
        //Add it up recursively to get the total size
        int size(Node* n) {
            if (n != nullptr) {
                int left = size(n->left);
                int right = size(n->right);
                int self = 1;
                return left + self + right;
            }
            return 0;
        }

        //Find the minimum Node value
        Node* findMin(Node* n){
            assert(n != nullptr);
            if (n->left != nullptr) {
                return findMin(n->left);
            }
            return n;
        }

        //this one is a beast
        //look through all the nodes recursively
        //once you find the node value there are numerous cases we need to look for
        //If the current node does not have left and right nodes, just delete it
        //If it does have a left or right node, set the child to the parent
        //If it has both left and right, we need to work some magic. First we find
        //the smallest value and set the node we want to delete to that value (removing it)
        void erase(int item, Node*& n) {
            if (n != nullptr) {
                if (item == n->data) {
                    if (n->right == nullptr && n->left == nullptr) {
                        delete n;
                        n = nullptr;
                    } else if (n->right == nullptr) {
                        Node* temp = n;
                        n = n->left;
                        delete n;
                    } else if (n->left == nullptr){
                        Node* temp = n;
                        n = n->right;
                        delete n;
                    } else {
                        Node *temp = findMin(n->right);
                        n->data = temp->data;
                        erase(item, n->right);
                    }
                } else if (item < n->data) {
                    erase(item, n->left);
                } else {
                    erase(item, n->right);
                } 
            }
        }

        //look through all the nodes
        //insert the node on the correct node, it will be added to the left if the value is less
        //added to the right if the value is greater
        void insert(int item, Node*& n) {
            if (n != nullptr) {
                if (item < n->data) {
                    insert(item, n->left);
                } else {
                    insert(item, n->right);
                }
            } else {
                n = new Node(item);
            }
        }
};

Let me know if you have any improvements or comments!

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Time limit is exhausted. Please reload the CAPTCHA.

This site uses Akismet to reduce spam. Learn how your comment data is processed.