CODEWITHSUNDEEP
c++data-structuresbinary-search-tree
Rrobinvip
Rrobinvip

Reputation: 119

BST in c++, return true or false when adding node

I'm learning C++ right now.

I want to set the return type of the add function in BST as bool, where it returns true if there is already a same item in the tree, and return false when it has been added to the tree.

Here is code, any suggestions on how to achieve this goal?

Code in the node class(.h file):

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

Code in the .cpp file:

BST :: BST() {
    root = NULL;
}

void BST :: add(string content) {
    root = insert(content, root);
}

any suggestions? Also this code is referencing from BST Implementation in C++

Upvotes: 0

Views: 371

Answers (1)

selbie
selbie

Reputation: 104559

Easiest approach is to do a search that identifies the parent node to insert at. I could show you tuples, but it's easier for now to just have an out parameter to indicate if the condition of "value already in tree" is an out parameter.

node* makeNode(const string& content)
{
    node* n = new node();        
    n->left = pNode->right = nullptr;
    n->data = content;
    return n;
}

node* BST::findLeafNode(const string& content, node* n, bool* alreadyExists)
{
    *alreadyExists= false;

    if (n == nullptr)
    {
       return nullptr; // this should only happen when root == nullptr
    }

    if (content == n->data)
    {
        *alreadyExists = true; // exact match
        return n;
    }

    if (content < n->data)
    {
        return (n->left ? findLeafNode(content, n->left) : n;
    }
    else
    {
        return (n->right ? findLeafNode(content, n->right) : n;
    }

}

bool BST::add(const string& content)
{
    bool alreadyExists = false;
    node* parent = findLeafNode(content, root, &alreadyExists);
    if (same)
    {
       return false;
    }
    node* n = makeNode(content);

    if (parent == nullptr)
    {
        root = n;
    }
    else
    {
        if (content < n->data)
        {
           n->left = n;
        }
        else
        {
           n->right = n;
        }
     }
     return true;
}

Upvotes: 1

Related Questions