Simple implementation of binary search tree in C++.

binary-search-tree-cpp.cpp

#include <iostream>
#include <math.h>
using namespace std;

template <class T>
struct Node {
    T value;
    Node *left;
    Node *right;

    Node(T val) {
        this->value = val;
    }

    Node(T val, Node<T> left, Node<T> right) {
        this->value = val;
        this->left = left;
        this->right = right;
    }
};

template <class T>
class BST {

    private:
    Node<T> *root;

    void addHelper(Node<T> *root, T val) {
        if (root->value > val) {
            if (!root->left) {
                root->left = new Node<T>(val);
            } else {
                addHelper(root->left, val);
            }
        } else {
            if (!root->right) {
                root->right = new Node<T>(val);
            } else {
                addHelper(root->right, val);
            }
        }
    }

    void printHelper(Node<T> *root) {
        if (!root) return;
        printHelper(root->left);
        cout<<root->value<<' ';
        printHelper(root->right);
    }

    int nodesCountHelper(Node<T> *root) {
        if (!root) return 0;
        else return 1 + nodesCountHelper(root->left) + nodesCountHelper(root->right);
    }

    int heightHelper(Node<T> *root) {
        if (!root) return 0;
        else return 1 + max(heightHelper(root->left), heightHelper(root->right));
    }

    void printMaxPathHelper(Node<T> *root) {
        if (!root) return;
        cout<<root->value<<' ';
        if (heightHelper(root->left) > heightHelper(root->right)) {
            printMaxPathHelper(root->left);
        } else {
            printMaxPathHelper(root->right);
        }
    }

    bool deleteValueHelper(Node<T>* parent, Node<T>* current, T value) {
        if (!current) return false;
        if (current->value == value) {
            if (current->left == NULL || current->right == NULL) {
                Node<T>* temp = current->left;
                if (current->right) temp = current->right;
                if (parent) {
                    if (parent->left == current) {
                        parent->left = temp;
                    } else {
                        parent->right = temp;
                    }
                } else {
                    this->root = temp;
                }
            } else {
                Node<T>* validSubs = current->right;
                while (validSubs->left) {
                    validSubs = validSubs->left;
                }
                T temp = current->value;
                current->value = validSubs->value;
                validSubs->value = temp;
                return deleteValueHelper(current, current->right, temp);
            }
            delete current;
            return true;
        }
        return deleteValueHelper(current, current->left, value) ||
               deleteValueHelper(current, current->right, value);
    }

    public:
    void add(T val) {
        if (root) {
            this->addHelper(root, val);
        } else {
            root = new Node<T>(val);
        }
    }

    void print() {
        printHelper(this->root); 
    }

    int nodesCount() {
        return nodesCountHelper(root);
    }

    int height() {
        return heightHelper(this->root);
    }

    void printMaxPath() {
        printMaxPathHelper(this->root);
    }

    bool deleteValue(T value) {
        return this->deleteValueHelper(NULL, this->root, value);
    }
};

int main() {
    BST<int> *bst = new BST<int>();
    bst->add(11);
    bst->add(1);
    bst->add(6);
    bst->add(-1);
    bst->add(-10);
    bst->add(100);
    bst->print();
    cout<<endl;
    cout<<"Nodes count: "<<bst->nodesCount();
    cout<<endl;
    cout<<"Height: "<<bst->height();
    cout<<endl;
    cout<<"Max path: ";
    bst->printMaxPath();
    cout<<endl;
    bst->deleteValue(11);
    cout<<"11 removed: ";
    bst->print();
    cout<<endl;
    cout<<"1 removed: ";
    bst->deleteValue(1);
    bst->print();
    cout<<endl;
    cout<<"-1 removed: ";
    bst->deleteValue(-1);
    bst->print();
    cout<<endl;
    cout<<"6 removed: ";
    bst->deleteValue(6);
    bst->print();
    cout<<endl;
    cout<<"-10 removed: ";
    bst->deleteValue(-10);
    bst->print();
    cout<<endl;
    cout<<"100 removed: ";
    bst->deleteValue(100);
    bst->print();
    cout<<endl;
    return 0;
}

Hey,
Thanks for sharing your implementation. It is a neat implementation. However, I have a question about the time complexity of your deletion. I saw in your deleteValueHelper function, you returned deleteValueHelper(current, current->left, value) || deleteValueHelper(current, current->right, value);
won't it be redundant? instead, you can check first whether the given value is bigger or lesser than your current.
Thanks

лапша

Добавьте в конструктор Node обнуление указателей
Node(T val) {
this->value = val;
this->left = this->right = nullptr; //C++11
//или this->left = this->right = NULL; //C++98
}

well done mate, nice implementation

very neat..I concur with chrisbangun

binary search tree without balancing......................)

very helpful thank you.

One question: What would be the easiest way to implement a deep copy constructor for the BST?

Does the line 15 should be this?

// add * after Node<T>
Node(T val, Node<T> * left, Node<T> * right)

good implementation

Hi guys, nice to meet you all especially seen the implementation of this BST in c++.
I am very junior on Algorithm and I would like anyone to assist me with basics to implement this BST and others in C++. The main challenge is that I am not good in C++ as well in such away that I don't know how to separate source file, main file and header file. Please, if anyone can redirect/point me where I can have the skills I will appreciate.
Rgds.

@dmakweba you can check out my implementation on BST here

make sure to initialize pointers in the constructor, otherwise, it will throw segmentation fault.
The line 12 should be this
Node(int val) : value(val) , left(NULL) , right(NULL) {}

To add to @xiuquanw's comment, the root variable in the BST class should be initialized to NULL. So instead of this:

Node<T> *root;

Add this:

Node<T> *root = NULL;

This is to ensure that when setting up the BST, the root is properly created in line 108.

memory leaks

root does not have to be initialised in C++ 11. Because no user-defined constructor is given for BST, the compiler implicitly defines a default constructor. During value-initialisation, fields will be zero-initialised because of the presence of this implicitly defined default constructor. Because pointers are a scalar type, they will be initialised to 0 i.e. NULL

@supratikn, of course, destructor is not implemented.