Binary search tree code giving out of resources error

67 views Asked by At

I was trying to create a binary search tree with insert, search and remove functions but when run, the program throwing an error " Killed exit status 137 -- Out Of Resources --" ,

#include <vector>
using namespace std;

class BST
{
public:
    int value;
    BST *left;
    BST *right;

    BST(int val)
    {
        value = val;
        left = nullptr;
        right = nullptr;
    }
    
    BST& insert(int val)
    {
        BST *current = this;
        
        while (current != nullptr)
        {
            if (val < current->value)
            {
                if (current->left == nullptr)
                {
                    current->left = new BST(val);
                    break;
                }
                else
                    current = current->left;
                
            }
            if (val > current->value)
            {
                if (current->right == nullptr)
                {
                    current->right = new BST(val);
                    break;
                }
                else
                    current = current->right;
            }
            
        }
        
        return *this;
    }
    
    bool contains(int val)
    {
        BST *current = this;
        while (current != nullptr)
        {
            if (val < current->value)
            {
                current = current->left;
            }
            else if (val > current->value)
            {
                current = current->right;
            }
            else if (val == current->value)
                return true;
            //else if(current ==nullptr)
            //return false;
        }
        
        return false;
    }
    
    BST& remove(int val)
    {
        BST *current = this;
        BST *parent = nullptr;
        while (current != nullptr)
        {
            if (val < current->value)
            {
                parent = current;
                current = current->left;
            }
            if (val > current->value)
            {
                parent = current;
                current = current->right;
            }
            if (val == current->value)
            {
                if (current->left != nullptr && current->right != nullptr)
                {
                    fnd(current->right);
                }
                else if (parent == nullptr)
                {
                    if (current->left != nullptr)
                    {
                        current->value = current->left->value;
                        current->right = current->left->right;
                        current->left = current->left->left;
                    }
                    else if (current->right != nullptr)
                    {
                        current->value = current->right->value;
                        current->left = current->right->left;
                        current->right = current->right->right;
                    }
                    else
                        current = nullptr;
                }
                else if (parent->left == current)
                {
                    if (current->left != nullptr)
                    {
                        parent->left = current->left;
                    }
                    else
                    {
                        parent->left = current->right;
                    }
                }
                else if (parent->right == current)
                {
                    if (current->left != nullptr)
                    {
                        parent->right = current->left;
                    }
                    else
                    {
                        parent->right = current->right;
                    }
                }
                
                break;
            }
        }
        
        return *this;
    }
    
    void fnd(BST *current)
    {
        BST *trav = current;
        BST *parent;
        while (trav->left != nullptr)
        {
            parent = trav;
            trav = trav->left;
        }
        current->value = trav->value;
        parent->left = nullptr;
    }
    
};
0

There are 0 answers