CODEWITHSUNDEEP
c++binary-search-tree
EgyptianFury
EgyptianFury

Reputation: 11

Binary search tree help insert function

My insert function compiles fine but if I try to add a 4th node it just replaces one of the first child nodes instead of adding a new one to those child nodes.

 bool bst::insert(string StudentName, int IDNumber) {

 class node *temp = root;
 class node *n=new node (StudentName, IDNumber);

    if (root==NULL) {
        root = n;
        return true;
    }
    if (temp -> ID == n->ID)
        return false;

    while (temp) {
        if (n-> ID < temp-> ID)
        { temp -> left = n;
            temp -> left -> parent= temp;
            temp = temp -> left;
            return true;
        }
        else
        {
            temp->right=n;
            temp -> right ->parent=temp;
            temp = temp -> right;
            return true;
        }
    }
    return false;
}

Upvotes: 1

Views: 2427

Answers (1)

Paweł Stawarz
Paweł Stawarz

Reputation: 4012

The problem in your code is inside the while loop. The loop will only run once, because you always return, in both cases. So, you only can add 3 nodes (or less, depending on the values), and you never actually check if a node already exists.

To fix this, you have to change your code to do the following:

while (temp) {
    if (n-> ID < temp-> ID)
    {
        if(temp->left)
            temp = temp->left
        else
        {
            temp -> left = n;
            temp -> left -> parent= temp;
            return true;
        }
    }
    else
    {
       // Analogously as for left
    }
}
return false; // This should never happen, but we have to return...

And I gotta admit, finding an answer wasn't hard

Upvotes: 1

Related Questions