I have written two C++ functions to insert a node in BST. One of the functions is working one is not

Question

This code is not working:

void BST::insertNode(BST *root,int d){
      if(root==NULL) {
        root = new BST(d);
        cout<<"Node inserted successfully\n\n";
        return;
      }
      if(root->data>d) return insertNode(root->left,d);
      if(root->data<d) return insertNode(root->right,d);
      if(root->data==d){ cout<<"Node already Exists\n\n";return;}
    }

This code is working:

void BST::insertNode(BST *root,int d){
  if(root->data>d){
    if(root->left==NULL){
      root->left = new BST(d);
      return;
    }
    else return insertNode(root->left,d);
  }
  if(root->data<d){
    if(root->right==NULL){
      root->right = new BST(d);
      return;
    }
    else return insertNode(root->right,d);
  }
}

Can anyone tell why is it happening. Because I think the first code should work as well. Please share your insights on it.

Answer 1

The both functions are incorrect.

For example the function that "works" does not check whether the passed pointer is equal to nullptr. So the first statement of the function

if(root->data>d){

can invoke undefined behavior.

The first function where such a test to equality to nullptr of the passed pointer is done does not work because it deals with a copy of the value of the original pointer used as an argument. Changing the copy within the function does not influence on the original pointer.

That is the main difference is that the first function deals with copies of values of pointers and the second function deals with original objects by accessing them through pointers to them as in this statement

if(root->left==NULL){
  root->left = new BST(d);

In this statement the original pointer left is accessed through the pointer to it root.

The first function needs to accept the original pointer by reference.

That is it must be declared like

void BST::insertNode( BST * &root, int d ){

Also as the function is a member function of the class then it should be declared as static.

That is you can have two functions in the class. The first one will be a public non-static member function with one parameter

insertNode( int d );

and the second one is protected or private static recursive function with two parameters

static insertNode( BST * &root, int d );

The first function will call the second function passing also the data member of the class root.