BST Recursive Insert

Question

I made a function to insert into BST using loops and it works fine. Now, when I write to do this using recursion, I don’t know why it does not work properly, however the logic is correct for me. It seems that the new node is not added to the BST tree, and the head of the tree after exiting the insert function becomes NULL again.

#include <iostream>
using namespace std;

class node{
public:
   int data;
   node *right;
   node *left;
   node(){
      data=0;
      right=NULL;
      left=NULL;
   }
};

class tree{
   node *head;
   int maxheight;
   void delete_tree(node *root);
public:
   tree(){head=0;maxheight=-1;}
   void pre_display(node* root);
   node* get_head(){return head;}
   void insert(int key,node* current);
};

void tree::insert(int key,node *current){
   if(current==NULL)
   {
      node *newnode=new node;
      newnode->data=key;
      current=newnode;
   }
   else{
      if(key<current->data)
         insert(key,current->left);
      else
         insert(key,current->right);
   }
   return;
}

void tree::pre_display(node *root){
   if(root!=NULL)
   {
      cout<<root->data<<" ";
      pre_display(root->left);
      pre_display(root->right);
   }
}

int main(){
   tree BST;
   int arr[9]={17,9,23,5,11,21,27,20,22},i=0;

   for(i=0;i<9;i++)
   BST.insert(arr[i],BST.get_head());

   BST.pre_display(BST.get_head());
   cout<<endl;

   system("pause");
   return 0;
}

Please tell me what I have to change in the algorithm for it to work.

Answer 1

In your insert function

void tree::insert(int key,node *current){
    if(current==NULL)
    {
        node *newnode=new node;
        newnode->data=key;
        current=newnode;
    }
    else{
        if(key<current->data)
            insert(key,current->left);
        else
            insert(key,current->right);
    }
    return;
}

you assign a new node, but never set BST :: head to a new allocated head. Therefore, BST :: get_head always returns null.

, node. root node BST:: head .

Answer 2

, node ! .

. insert, , :

void tree::insert(int key, node **current)
{
    if(*current == NULL)
    {
        node *newnode = new node;
        newnode->data = key;
        *current = newnode;
    }
    else 
    {
        if(key < (*current)->data)
            insert(key, &(*current)->left);
        else
            insert(key, &(*current)->right);
    }
}

:

BST.insert(arr[i], &BST.get_head());  // Note the ampersand (&)

Answer 3

             node  tree:: insert ( int key , node * current )  {

                     if ( ! current ) {
                           node * newnode = new node ;
                           newnode -> key = key;
                           current = newnode ;
                      }
                    else if ( key < current -> key )  {
                        current -> left = insert ( key , current ->left 
                         }
                    else 
                       current -> right = insert ( key , current->right )
                return current ;
               }

.... jsut node , node, node.

Answer 4

void tree::insert(int key,node*& current){
  if(current==NULL)
  {
    node *newnode=new node;
    newnode->data=key;
    current=newnode;
  }
  else{
    if(key<current->data)
      insert(key,current->left);
    else
      insert(key,current->right);
  }
  return;
}

.

Answer 5

struct node{
    node* left;
    node* right;
    int data;
};

node* root=NULL;

node* create(node* head,int val){
    if(head==NULL){
        node* nn=new node;
        nn->data=val;
        nn->left=NULL;
        nn->right=NULL;
        head=nn;
    }
    else if(val<head->data)
        head->left=create(head->left,val);
    else if(val>head->data)
        head->right=create(head->right,val);
    return head;
}

int main(){
    int num=0;
    cout<<"Enter value in tree or press -1 to Exit\n";
    while(num!=-1){
        cin>>num;
        if(num==-1){
            cout<<"\nTree Created\n";
            break;
        }
        else{
            root=create(root,num);
        }
    }
}

,