CODEWITHSUNDEEP
c++treebinary-tree
user6185425
user6185425

Reputation:

Can't insert a new node in the binary tree

I believe my insertion function is right, but it looks like the new node is not being inserted in the tree. I could not figure out where is the mistake. I appreciate any help,thanks.

There is the declaration of node and tree:

class Node{
     int key;
     Node *right, *left;
}

class Tree{
public:
      int init();
      Node *root;
      Node *insert(int key, Node *p);
};

there is the functions:

int Tree::init(){
    this->root = NULL;  return 1;
}

Node *Tree::insert(int key, Node *p){
  if(p == NULL){
    Node *novo = new Node();
    novo->key = key;
    novo->left = NULL;
    novo->right = NULL;
    p = novo;
    }
  else if(key < p->key){ p->left = insert(key, p->left); }
  else if(key > p->key){ p->right = insert(key, p->right); }
  else{ cout << "Error: key already exist" << endl; }

return p;
}

When I call the function in the main, it looks like it does not link the new node

int main() {
    Tree dictionary;

    cout << "enter the key"; cin >> key;   

    dictionary.insert(key, dictionary.root);

    cout << dictionary.root->key;
}

Upvotes: 1

Views: 857

Answers (1)

Christophe
Christophe

Reputation: 73376

In your insert() function, when the tree is empty or if you've reached the last node, you create a new node: 

if(p == NULL){
   Node *novo = new Node();
   novo->key = key;
   novo->left = NULL;
   novo->right = NULL;
   p = novo;              // ouch !!!! 
   }

Unfortunately, the statement p=novo only updates the local parameter p of your function. Its value will vanish as soon as you return from the function. It will not update the pointer with which you've called your function. So the root of your tree remains NULL (or the left/right pointer of the last node).

To get the effect that you expect (i.e. your p assigment updates the root pointer or the pointer to left/right of the last node), you need to change the signature to: 

  Node *insert(int key, Node *& p);   // p is passed by reference

This will pass the pointer p by reference. Modifying p will then have the effect of modifying the pointer you used to call the function, and will endure a lasting effect of the insertion.

Upvotes: 1

Related Questions