Recursive insertion of BST

Question

I have made a function for insertion in BST using loops and it is working perfectly fine. Now, when iam writing to do it using recursion i don't know why it's not working properly, however the logic is correct according to me. It seems that no newnode is being added to the BST tree and head of the tree after coming out of the insertion function is again becoming NULL.

#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 should i change in the algorithm to make it work.

Ioneionesco

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 allocate a new node but never set BST::head to newly allocated head. So BST::get_head will always return null.

One way to fix this would be for insert to return a node. This would be root node in your case and set the BST::head to this value.

Divestiture

But iam sending head pointer from main, and hence current will be same as the head in the first instance of recursion. – Ioneionesco

You are passing a node* by value. If you pass it by reference BST::head will be updated correctly – Divestiture

But i want to keep BST head private. – Ioneionesco

@Zohaib: does private mean for you that it should never change? – Citronella

If you want to keep things private.... Node should be class private to BST and BST should only expose iterators to iterate the tree. – Divestiture

Answer 2

Your recursion looks fine, but you don't actually add the node anywhere! You just recurse through the tree.

Edit You can change the insert method to take a pointer to a pointer, like this:

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);
    }
}

And in main call it like this:

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

Saintebeuve

@Ioneionesco No, you just create a new node, you don't add it to the tree. – Saintebeuve

Does'nt this statement:current=newnode; would add newnode to the tree. – Ioneionesco

@Ioneionesco Oops, missread it. The indentation is not too good in my opinion. – Saintebeuve

@Ioneionesco Yeah, getting a little tired over here, end of day, know what's wrong, will look at it later. – Saintebeuve

Answer 3

you should try this

             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 ;
               }

it works fine....jsut update the head node every time whenver a new node is inserted and it will return the updated current node.

Kiel

Answer 4

Just change your function as

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;
}

make your input pointer as a reference parameter.

Drennan

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);
        }
    }
}

hope this code solves your problem

Slung

Answer 6

void insertNode_recursive(int value, TreeNode *current)
{
    if (current == NULL)
    {
        if (current == NULL && isEmpty())
        {
            TreeNode *new_node = new TreeNode(value);
            current = new_node;
            root = new_node;
        }
        else
        {
            TreeNode *new_node = new TreeNode(value);
            current = new_node;
        }
    }
    else
    {
        if (value < current->getValue())
        {
            insertNode_recursive(value, current->getLeft());
        }
        else if (value > current->getValue())
        {
            insertNode_recursive(value, current->getRight());
        }
        else
        {
            cout << "\nDuplicate Value are Not Allowed\n";
        }
    }
}

This Code is Useful For Recursively Print the Tree Node

Ambala