Inserting into a binary search tree

Suede picture Suede · Oct 24, 2013 · Viewed 11.9k times · Source

I wrote a function to insert nodes into a binary search tree. However, when trying to build a solution in Visual Studio 2013, I receive this: "Unhandled exception at 0x00FD4CD0 in BST.exe: 0xC0000005: Access violation reading location 0xCCCCCCCC." The following is my code.

void BST::insert(int value) {
    Node* temp = new Node();
    temp->data = value;
    if(root == NULL) {
        root = temp;
        return;
    }
    Node* current;
    current = root;
    Node* parent;
    parent = root;
    current = (temp->data < current->data) ? (current->leftChild) : (current->rightChild);
    while(current != NULL) {
        parent = current;
        current = (temp->data < current->data) ? (current->leftChild) : (current->rightChild);
    }
    if(temp->data < parent->data) {
        parent->leftChild = temp;
    }
    if(temp->data > parent->data) {
        parent->rightChild = temp;
    }
}

Then in my main function I have:

int main() {
    BST bst;
    bst.insert(10);
    system("pause");
}

When I remove bst.insert(10); in my main function, I no longer receive the unhandled exception.

The following is the initialization of my struct

struct Node {
    int data;
    Node* leftChild;
    Node* rightChild;
    Node() : leftChild(NULL), rightChild(NULL) {} 
};
struct BST {
    Node* root;
    void insert(int value);
    BST() : root(NULL) {}
};

Answer

digital_revenant picture digital_revenant · Oct 24, 2013

In your insertion function you are not setting leftChild and rightChild to NULL.

void BST::insert(int value) {
    Node* temp = new Node();
    temp->data = value;
    temp->leftChild = NULL;
    temp->rightChild = NULL;
    if(root == NULL) {
        root = temp;
        return;
    }

Also, I cannot be sure (as you have not posted the constructor for BST) but you may not have set root to NULL in the BST constructor. Try with these modifications.

Seems like you do not have a constructor in BST from what you have posted:

struct BST {
    Node* root;
    void insert(int value);
    BST(): root(NULL) { } // add a constructor to initialize root to NULL
};