Create BST from array of strings

Question

I've been trying to create a functionality in C++ that can implement a BST from an array of strings, but it doesn't do anything at all and I don't understand what might be the problem. It should work recursively with for loop to iterate through all strings in an array.


void insertNode(node* root, std::string name)
{
    if (root == nullptr)
    {
        node* n = new node;
        n->name_ = name;
        root = n;
    }
    else if (root->name_.compare(name) <= 0)
    {
        insertNode(root->right_, name);
    }
    else
    {
        insertNode(root->left_, name);
    }
}

void CreateBST(node_t *& root, const std::vector<std::string> & array)
{   
    for (int i = 0; i < array.size(); i++)
    {
        insertNode(root, array[i]);
    }
}

I've tried to wirte recursive function to create a BST, while comparing strings from an array to set them as nodes.

For changes to root to have an effect outside insertNode it needs to be node**. — 500 - Internal Server Error
– 500 - Internal Server Error, Commented Apr 5, 2022 at 16:08
FYI, you can use comparison operators: <, >, ==, !=, <=, >=, with std::string instead of the compare() method. IMHO, easier to read using the comparison operators. — Thomas Matthews
– Thomas Matthews, Commented Apr 5, 2022 at 16:23
@Alessa when I've wrote last compare is obsolete I meant condition is obsolete since is covered by earlier if (you are in else section of it), code below is still needed. — Marek R
– Marek R, Commented Apr 5, 2022 at 16:46

jwezorek · Accepted Answer · 2022-04-06 23:23:22Z

1

The problem with your code is this line

void insertNode(node* root, std::string name)

You need root there to be a node* reference (i.e. node*&) otherwise when you set node to a new value in the function that change is lost to the calling code.

Other possible issues include a typo where you use node_t in the other function, and you need to make sure that the node default constructor is nulling out the two pointers to children because your code assumes those pointers will be null after creation.

edited Apr 6, 2022 at 23:23

answered Apr 5, 2022 at 16:17

jwezorek

10k2 gold badges37 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Create BST from array of strings

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related