CODEWITHSUNDEEP
c++cdata-structuresbinary-treebinary-search-tree
Justin Carrey
Justin Carrey

Reputation: 3851

non recursive binary tree insert() method not working

I have written a binary tree code for inserting elements into it in non-recursive method. The code is not working as intended. Regardless of how many times I debug the code, nothing seems to be wrong but I am getting wrong results. I am hoping you guys can help. Thanks in advance.

void insert(int element){
    if(root == NULL){
        struct elemq *node;
        node = (struct elemq *)malloc(sizeof(struct elemq));
        node->ele = element;
        node->left = NULL;
        node->right = NULL;
        root = node;
        cout << root->ele << "\n";
    }
    else{
        struct elemq *ref;
        ref = root;
        while(ref != NULL){
            if(element <= ref->ele){
                if(ref->left == NULL){
                    struct elemq *node;
                    node = (struct elemq *)malloc(sizeof(struct elemq ));
                    node->ele = element;
                    node->left = NULL;
                    node->right = NULL;
                    ref->left = node;
                    break;
                }
                else{
                    ref = ref->left;
                }
            }
            else if(element > ref->ele){
                if(ref->right == NULL){
                    struct elemq *node;
                    node = (struct elemq *)malloc(sizeof(struct elemq ));
                    node->ele = element;
                    node->left = NULL;
                    node->right = NULL;
                    ref->right = node;
                    break;
                }
                else{
                    ref = ref->right;
                }
            }
        }
    }
}

Every time I try to insert an element, each element is being treated as root, not only the first time. So, every time, the condition if(root == NULL) is true. I declared root as global variable and initialized it to NULL in main(). I came to know this by putting cout << in the first if() condition. I modified my previous post to this new question.

Upvotes: 1

Views: 2250

Answers (2)

Adam Schmidt
Adam Schmidt

Reputation: 452

I think you are mistakenly setting the node that you are adding to the references, instead of setting the left and right references to the node you are adding. Change node = ref->left to ref->left = node, and likewise for the right.

Upvotes: 1

dchhetri
dchhetri

Reputation: 7136

node = ref->left;

You want

ref->left = node;

and similar for the ref->right

Upvotes: 2

Related Questions