Binary Search Tree having issues with insert function

Question

I'm using recursive functions to insert a node into my binary search tree. The program works by creating a root node if there is none. Root is a pointer to a node struct. If the root already exists I call the worker function.

Note: Key is int and Item is a string.

When calling the worker function, current->key(-858993460) and current->item(Error reading characters of string) are not their expected values (1, "Harrold").

Recursion continues until this Exception occurs:

"Exception thrown: read access violation. current was 0xCCCCCCCC."

Key k and Item i are their expected value. It is only why I'm trying to access them from Node* root that they change and I'm unsure why this is happening.

Any help is appreciated

void BST::insert(Key k, Item i)
{
    if (root == nullptr) {
        root = &Node(k, i);
    }
    else insertRec(k, i, root);
}

void BST::insertRec(Key k, Item i, Node* current)
{

    if (current->key == k)//if the key of the inserted node is = to an existing key, change the item.
    {
        current->item = i;
    }
    else if (current->key > k)//if the key of the current node is larger than key inserted traverse leftchild recursively calling function
    {
        if (current->leftChild != nullptr)
            insertRec(k, i, current->leftChild);
        else
            current->leftChild = &Node(k, i);
    }
    else if (current->key < k)
    {
        if (current->rightChild != nullptr)
            insertRec(k, i, current->rightChild);
        else
            current->rightChild = &Node(k, i);
    }
}

current->leftChild = &Node(k, i); -- Explain what this weird looking line does. What's the reason for storing a pointer to a temporary (which is doomed for failure)? Second, please post a minimal reproducible example — PaulMcKenzie
Node is a struct. It contains Int key, String item, Node* leftChild and Node* rightChild. struct BST::Node What I'm trying to do here is; 1-Create a new node. 2-Create it as the current node's right or left child so it has a parent. — JohnDoe
Is what you're trying to do is to create a new Node? What does your book and many examples show how to create new objects? What you're doing is creating a temporary. Ever hear of new in C++, or better yet std::unique_ptr<> and make_unique? If not, then your entire existing BST is not built correctly, way before the insert is called. — PaulMcKenzie
Hi Paul, The problem was the leftChild and rightChild were not initialized to nullptr. So when the program reached this if (current->leftChild != nullptr) it wouldn''t operate the code. Also replacing &Node(k, i) with new Node(k, i) let me access current->key. Thanks for your help — JohnDoe

PaulMcKenzie PaulMcKenzie · Accepted Answer · 2017-11-11T12:33:24

What you're doing now in creating new nodes for the tree is that you're instantiating a temporary Node object and then storing the address of that object. This is what &Node(k, i) is doing.

The problem is that the temporary will go out of scope, and your BST now contains Node pointers pointing to something that doesn't exist. That's more likely the reason your program stops with invalid address errors.

So instead of

&Node(k,i),

use

new Node(k, i).

This dynamically allocates a new Node, making the pointer to this Node "stick" and not be temporary.

Then of course, you're responsible for deallocating the memory for the BST when it's time to destroy the tree. That's when you need to go through the tree nodes and call delete on each Node.

Binary Search Tree having issues with insert function

1 Answers