Question

Q. write the algorithm for each function in this code:

void insert(int x, node*&p)
{
//cheak if the pointer is pointing to null.
if (p==NULL)
{
    p = new node;
    p->key=x;
    p->left=NULL;
    p->right=NULL;
}
else
{
    //Cheak if the element to be inserted is smaller than the root.
    if (x < p->key)
    {
      //call the function itself with new parameters.
      insert(x,p->left);
    }
    //cheak if the alement to be inserted is greater then the root
    else if (x>p->key)
    {
      //call the function itself with new parameters.
      insert(x,p->right);
    }
    else
    {
      cout<<"Element already Exits! \n";
    }
}
}

void search (int x, node *&p)
{
node*tempP=p;
if(p==NULL)
{
    cout<<"Tree is Empty \n";
}
else
{
    while(p != NULL)
    {
      if(x < p->key)
      {
        p=p->left;
      }
      else if (x>p->key)
      {
        p=p->right;
      }
      else
      {
        cout<<"Element found\n";
        p= tempP;
        return;
      }
    }
   p= tempP;
   cout<<"Element NOT found \n";
}
}

//traverse from left to root to right
void inorder(node*p)
{
if(p== NULL)
{
    return;
}
else
{
    inorder(p->left);
    cout<<p->key<<"\t";
    inorder(p->right);
}
}

void preorder(node*p)
{
if(p==NULL)
{
    return;
}
else
{
    cout <<p->key <<"\t";
    preorder(p->left);
    preorder(p->right);
}
}

void postorder(node*p)
{
if(p==NULL)
{
    return;
}
else
  {
    postorder(p->left);
    postorder(p->right);
    cout<<p-> key<<"\t";
}
}

void remove(int x, node*&p)
{
   if (p ==NULL)
   {
     cout<<"Element NOT found\n";
   }
   //traverse left or right to reach the node to be //deleted
   else if (x < p->key)
   {
     remove(x,p->left);
   }
   else if (x > p->key)
   {
     remove(x,p->right);
   }
   //case 1: delete leaf node
   else if ((p->left == NULL) && (p->right ==NULL))
   {
     p=NULL;
   }
   // case 2: delete node with one child
   else if (p->left == NULL)
   {
     p=p->right;
   }
   else if (p->right ==NULL)
   {
     p=p->left;
   }
   //case 3: delete node with two children
   else
   {
     p->key=deletemax(p->left);
   }
}

int deletemax(node*&p)
{
   node* temp;
   int num;
   cout<<"Delete max number \n";
   if(p->right == NULL)
   {
     num=p->key;
     p=p->right;
     return num;
   }
   else
   {
   num=deletemax(p->right);
   }
}};

Answer 1

//algorithm for insert method
input:x,root
step1)starting from root, if root is empty then create new node with data x and point it to root
step2)if root is not empty, compare the inserting element with root element, if less than root element then recurse left, if greater than root recurse right, if eqaul then print already exist

//algorithm for search method
input:x,root//p
step1)if root is empty print: tree is empty
step2)if root is empty,loop it to: compare the x element with root(p), if less than root then change root to left pointer, if greater than root then change root to right pointer, if eqaul then print Element found and return from method, iterate until root is empty
step3)print Not found

//algorithm for inorder:
step1)traverse left subtree
step2)visit root
step3)traverse right subtree

//algorithm for preorder:
step1)visit root
step2)traverse left subtree
step3)traverse right subtree

//algorithm for postorder:
step1)traverse left subtree
step2)traverse right subtree
step3)visit root

//algorithm for remove method
input: x,root
step1)if root is empty then print :element not found
step2)if root is not empty, then compare x with root element, if x less then root then recurse left, if x greater than root then recurse right
step3)if x equals root, if it has 0 child's then simply delete it, if it has one child then directly update link with child node, if it has two childs then call deletemax

//algorithm for deletemax
step1)recursively traverse right until a leaf node is found
step2)then return//which is max node