CODEWITHSUNDEEP
c++algorithmbinary-search-tree
Ali
Ali

Reputation: 5476

Binary Search Tree Insertion C++

Maybe asked million times before but I simply cannot understand what's wrong with this. I didn't want to use any code on the internet so I've just tried to program what's on my mind. Either this or my print function is wrong. Is there anything wrong with the code below?

void addNode(int value)
    {
        Node* newNode=new Node;
        newNode->data=value;
        if(root==NULL)
            root=newNode;
        else {
            Node* temp=root,*parent;
            while(temp!=NULL)
            {
                parent=temp;
                if(temp->data == value)
                    return;
                else if(temp->data < value)
                    temp=temp->left;
                else 
                    temp=temp->right;
            }
            temp=newNode;
        }
    }

Upvotes: 3

Views: 2742

Answers (1)

Mike Seymour
Mike Seymour

Reputation: 254431

temp=newNode;

This assigns the pointer to a local variable, which is discarded when the function returns, losing the new node. Instead, you want to assign it to a pointer within the tree; perhaps something like:

if (temp->data < value) {        // If the new node should be to the left
    if (temp->left) {            //   If there is a left subtree
        temp = temp->left;       //      Move into the left subtree
    } else {                     //   Otherwise
        temp->left = newNode;    //      Insert the new node there
        return;                  //      Done.
    }
}

and likewise for temp->right if value < temp->data.

Also:

if (temp->data == value) 
    return;

You have a memory leak there; you should delete newNode before returning.

Upvotes: 6

Related Questions