Binary Search Tree Implementation in C++

Binary Search Tree.cpp

/* 
** Binary Search Tree implementation in C++
** Harish R
*/
#include<iostream>
using namespace std;

class BST {
    
    struct node {
        int data;
        node* left;
        node* right;
    };

    node* root;

    node* makeEmpty(node* t) {
        if(t == NULL)
            return NULL;
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        return NULL;
    }

    node* insert(int x, node* t)
    {
        if(t == NULL)
        {
            t = new node;
            t->data = x;
            t->left = t->right = NULL;
        }
        else if(x < t->data)
            t->left = insert(x, t->left);
        else if(x > t->data)
            t->right = insert(x, t->right);
        return t;
    }

    node* findMin(node* t)
    {
        if(t == NULL)
            return NULL;
        else if(t->left == NULL)
            return t;
        else
            return findMin(t->left);
    }

    node* findMax(node* t) {
        if(t == NULL)
            return NULL;
        else if(t->right == NULL)
            return t;
        else
            return findMax(t->right);
    }

    node* remove(int x, node* t) {
        node* temp;
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            t->left = remove(x, t->left);
        else if(x > t->data)
            t->right = remove(x, t->right);
        else if(t->left && t->right)
        {
            temp = findMin(t->right);
            t->data = temp->data;
            t->right = remove(t->data, t->right);
        }
        else
        {
            temp = t;
            if(t->left == NULL)
                t = t->right;
            else if(t->right == NULL)
                t = t->left;
            delete temp;
        }

        return t;
    }

    void inorder(node* t) {
        if(t == NULL)
            return;
        inorder(t->left);
        cout << t->data << " ";
        inorder(t->right);
    }

    node* find(node* t, int x) {
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            return find(t->left, x);
        else if(x > t->data)
            return find(t->right, x);
        else
            return t;
    }

public:
    BST() {
        root = NULL;
    }

    ~BST() {
        root = makeEmpty(root);
    }

    void insert(int x) {
        root = insert(x, root);
    }

    void remove(int x) {
        root = remove(x, root);
    }

    void display() {
        inorder(root);
        cout << endl;
    }

    void search(int x) {
        root = find(root, x);
    }
};

int main() {
    BST t;
    t.insert(20);
    t.insert(25);
    t.insert(15);
    t.insert(10);
    t.insert(30);
    t.display();
    t.remove(20);
    t.display();
    t.remove(25);
    t.display();
    t.remove(30);
    t.display();
    return 0; 
}

honestly, you should learn them separately, then tie them together when you understand enough

Best and simple. Perfect 10/10.

Best and simple. Perfect 10/10.

How is it ""best and simple" when it doesn't even work properly? More like "perfect 10/10" to get you fired or to fail a class.

bro i have this bst code which runs perfectly

Ok? How so? I haven't seen this changed and this code still throws segfaults everywhere. Not to mention, using the search function in this code will actually modify the list. How can you say something runs perfectly when a read operations causes an unexpected write?

my functions work fine but it does not throw segment errors

…

On Mon, 1 Mar 2021, 11:16 pm werlious, ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ Ok? How so? I haven't seen this changed and this code still throws segfaults everywhere. Not to mention, using the search function in this code will actually modify the list. How can you say something runs perfectly when a read operations causes an unexpected write? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <https://gist.github.com/a7df7ce576dda35c9660#gistcomment-3649679>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ASLSXLLZBZBXM24HDFNBF43TBPKXTANCNFSM4IBGEXZQ> .

You say "my functions". have you changed the code after you copied it? Or are you trying to boost the OPs gist without having tried it? Because its about as plain as day the amount of bugs in this code. For example. I mentioned the broken search function.
Function in question:

    void search(int x) {
        root = find(root, x);
    }
//...
 node* find(node* t, int x) {
        if(t == NULL)
            return NULL;
        else if(x < t->data)
            return find(t->left, x);
        else if(x > t->data)
            return find(t->right, x);
        else
            return t;
    }

Where, in any BST (find one other than this), would the search function not only not return a result, but would also fragment the entire list?
Because I'm not sure how well versed you are in general programming, but if you look at that search (and its supporting find) method, you can very clearly see that anytime search is called, the root of the list will be set to the searched value if found else null. You can say it works and its perfect all you want, but the proof is in the pudding.

Now, because I have a good feeling your still going to try and defend this bad piece of code saying its somehow perfect, let me enlighten you, and hopefully teach you something to keep you from failing again in the future.
Let's say the BST contains 2,3,6,8,10.
Lets say I search for 8.
find will recurse until it finds 8, then return the node holding 8 to search, which will set the root of the list to that node.
Assuming the tree is structured like:

   6
 3  8
2    10

Then you've just lost your pointers to 6,3,2 because this broken search will change the list to:
8
10

without even deconstructing the nodes. So yes, this WILL/DOES segfault. And thats ignoring the fact that a 'normal' bst search would return a boolean, not be void. If you want, I can tear apart the rest of this bogus code and show you exactly how bad it is (its bad)

Honestly, severely misleading information such as this should not be allowed on Github period. Atleast not publicly with random no ones claiming it works "perfectly"

Hi,
I am a student at the University of Akron studying Computer Engineering. One of my class projects is to implement an AVL tree. I need to compare my tree implementation with some other trees for search, insert, and delete operations. There's no open source license on your BST implementation - may I have your permission to run test cases on your code for this project?
Thanks,
Elena Falcione
[email protected]

Hi,
I am a student at DAIICT, India. Studying ICT with machine learning specialization. This is an article, I have written while practicing the algorithms. I gathers a lot of information and wrote this articles of a binary tree in java: this is the link-> Click here

Hello @harish-r! In your implementation of BST search, you are changing the root of the tree every time you search. This is undesired behavior in a BST.

Perhaps there's a mistake in search() since it's just a public interface "returning" what find() returns. Thus root MUST NOT BE MODIFIED
Once it's fixed, everything is good.