Binary Tree Problem

[letterG]

Hi all!

I've just started working on my Binary Search Tree and already there's a problem that I can't seem to understand. Ok here's the problem, when I compile its ok but when I run it there's an error, i've managed to found where the problem is but I don't understand why..I will comment the part where there seems to be a runtime error.

#include<iostream>
using namespace std;

class treeNode{
    public:
    int item;
    treeNode *left;
    treeNode *right;
    treeNode();
};

treeNode::treeNode(){
    item=0;
    left=right=NULL;
}

class binarySearchTree{
    private:
    int size;
    public:
    treeNode *root;
    binarySearchTree();
    void insert(int);
    void del(int);
    void search(int);
    void display();
};

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

void binarySearchTree::insert(int x){
    treeNode *temp;
    treeNode *add;

    add = new treeNode;
    add->item=x;
    temp=root;

    if(temp==NULL)
        root=add;
    else{
        while(temp!=NULL){
            if(temp->item>=add->item)
                temp=temp->left;////////////It's here that I encounter the runtime error..why is this?
            else
                temp=temp->right;
        }
        temp=add;
    }
}

void binarySearchTree::display(){
    while(root!=NULL){
        cout<<root->item<<endl;
        root=root->left;
    }
}

int main(){
    binarySearchTree x;

    x.insert(1598);
    x.insert(160);
    x.display();
    return 0;
}

[tinstaafl]

What error are you getting? When I run your code, I don't think it's doing everything you want but it doesn't return any errors.

[letterG]

I've run it just now and it isn't a runtime error as I previously mentioned, sorry. The thing is when I display it only displays the first number, seems like it isn't connecting the next number and I just can't figure it out...any ideas?

[deceptikon]

What's wrong here:

while(temp!=NULL){[...]}
temp=add;

If temp is NULL after the loop then it no longer refers to the tree in any way. So assigning add to temp will accomplish absolutely nothing when insert() returns.

This was actually a stumbling block for me when I first started learning referential data structures. A null pointer isn't a part of the structure, and as soon as you set your reference into the data structure to null, you're done with it. To insert a node where a null currently resides, you must have a reference to the previous node:

while (true) {
    if (temp->item >= add->item) {
        if (temp->left == NULL)
            break;

        temp = temp->left;
    }
    else {
        if (temp->right == NULL)
            break;

        temp = temp->right;
    }
}

if (temp->item >= add->item)
    temp->left = add;
else
    temp->right = add;

There are a number of ways to do it, of course, but the above highlights the fact that as soon as temp becomes null, you're screwed.

[RonalBertogi]

Let's examine the code in your binarySearchTree::insert() function line by line:

treeNode *temp;
treeNode *add;

here you allocated memory for you local add variable and set its item property
to the value of x

add = new treeNode;
add->item=x;
temp=root;
if(temp==NULL)

this line here will be executed the first time insert() is called since root is
initialized to NULL in this class' constructor.

    root=add;

root->item now is equal to 1598

else{

This code block here will then be executed in the succeeding calls to the function beccause root is no longer NULL, reiterating until temp becomes NULL. But no matter how many times will this block loop, this does actually nothing to insert the new value which is 160 in your second call.

    while(temp!=NULL){
        if(temp->item>=add->item)
            temp=temp->left;////////////It's here that I encounter the runtime error..why is this?
        else
            temp=temp->right;
    }

Even this line here would not affect your root member. Doing nothing significant.

    temp=add;
}

Hope this could help you.

[letterG]

but isn't the last null that the temp points to is in the case the root->left?. Also thanks much for your help guys and deceptikon in particular as its the one that made me understand what my problem was..but still it bothers me..why didn't it point to root->left?, just the way C++ works?

[deceptikon]

but isn't the last null that the temp points to is in the case the root->left?

It is, but in C++ all null pointers are the same. Once temp becomes null, you have no way of determining which node pointed to it. You can think of it like this (using a simple tree):

[letterG]

Ah I see, that image helps a lot for me to understand it..thanks again!