Question

I am trying to implement a search function for a binary search tree.

I am trying to get the output to print each element preceding the the target of the search. For example, in the code when I search for 19, the output should be "5-8-9-18-20-19"

Please only modify the search function and also please walk me through what I did wrong. I am trying to figure this out.

Here is my code:

#include<iostream>
using namespace std;

class node
{
public:
   int data;
   node *left;
   node *right;
};

class BST
{
public:
   BST()
   {
       root = NULL;
   }

   void insert(int element)
   {
       node *newptr = new node;
       newptr->data = element;
       newptr->left = NULL;
       newptr->right = NULL;
       //cout << "Here" << endl;

       if (root == NULL)
       {
           root = newptr;
       }
       else
       {
           node *p = root;
           node *parent = NULL;
           while ((p != NULL) && (p->data != element)) //find the right location for the new node
           {
               if (element < p->data)
               {
                   parent = p;
                   p = p->left;
               }
               else
               {
                   parent = p;
                   p = p->right;
               }
           }

           if (p == NULL) //if the element is not in the BST
           {
               if (element < parent->data)
                   parent->left = newptr;
               else
                   parent->right = newptr;
           }
           else
               cout << "node duplicate!" << endl;
       }
   }

   void remove(int element)
   {
       node *p = root;
       node *parent = NULL;
       while ((p != NULL) && (p->data != element)) //find the correct location for the new node
       {
           if (element < p->data)
           {
               parent = p;
               p = p->left;
           }
           else
           {
               parent = p;
               p = p->right;
           }
       }

       if (p->left == NULL && p->right == NULL) //case 1
       {
           if (element < parent->data)
               parent->left = NULL;
           else
               parent->right = NULL;
           delete p;
       }

       else if (p->left != NULL && p->right == NULL) //case 2
       {
           if (element < parent->data)
               parent->left = p->left;
           else
               parent->right = p->left;
           delete p;
       }

       else if (p->left == NULL && p->right != NULL) //case 2
       {
           if (element < parent->data)
               parent->left = p->right;
           else
               parent->right = p->right;
           delete p;

       }

       else //case 3
       {
           int min_of_right_child = findmin(p->right);
           remove(min_of_right_child);
           p->data = min_of_right_child;
       }

   }

   int findmin(node *p)
   {
       while (p->left != NULL)
           p = p->left;
       return p->data;
   }

   int findmax(node *p)
   {
       while (p->right != NULL)
           p = p->right;
       return p->data;
   }

   void inorder(node *p)
   {
       if (p != NULL)
       {
           inorder(p->left);
           cout << p->data << " ";
           inorder(p->right);
       }

   }

   void preorder(node *p)
   {
       if (p != NULL)
       {
           cout << p->data << " ";
           preorder(p->left);
           preorder(p->right);
       }

   }

   void postorder(node *p)
   {
       if (p != NULL)
       {
           postorder(p->left);
           postorder(p->right);
           cout << p->data << " ";

       }

   }

   void traversal()
   {
       cout << " Min value: " << findmin(root);
       cout << " Max value: " << findmax(root);
       cout << " Inorder: ";
       inorder(root);
       cout << " Preorder: ";
       preorder(root);
       cout << " Postorder: ";
       postorder(root);
       cout << endl;
   }

  

int search(int x)
   {
       node *t = root;

       while (t != NULL) {
           if (x < t->element){
               t = t->left;
               cout << t << "-";
           }
           else if (x > t->element){
               t = t->right;
               cout << t << "-";
           }
           else
               cout << endl;
               return t; // Match
       }
       return NULL; // Not found

   }

private:
   node *root;

};

void main()
{
   BST *t1 = new BST();
   t1->insert(5);
   t1->insert(8);
   t1->insert(3);
   t1->insert(1);
   t1->insert(4);
   t1->insert(9);
   t1->insert(18);
   t1->insert(20);
   t1->insert(19);
   t1->insert(2);
   t1->traversal();
   t1->search(3);
   t1->search(18);
   t1->search(19);
   t1->remove(9);
   t1->traversal();
   t1->remove(2);
   t1->traversal();
   t1->remove(8);
   t1->traversal();
   t1->remove(3);
   t1->traversal();
   t1->remove(5);
   t1->traversal();

}

Answer 1

Below is the modified search function. I have added the text "Searching for ", for clarity.

int search(int x)
   {
        node *t = root;
        cout<<"Searching for "<<x<<": ";
      
       while (t != NULL) {
           if (x < t->data){
               cout << t->data << "-";
               t = t->left;
           }
           else if (x > t->data){
               cout << t->data << "-";
               t = t->right;
           }
           else {
               cout << t->data << endl;
               return t->data; // Match
           }
       }
       return NULL; // Not found

   }

Screenshot of the output after modifying search function:

Below are the things that you did wrong:

1. if (x < t->element) should be if (x < t->data), because the name of the member variable is data. Similarly, else if (x > t->data) should be else if (x > t->data).
2. You should print the value (cout<<t->data<<"-";) before changing the current node (t = t->left), because otherwise you will miss the current value.
3. Print the value of current node in the last else statement, that is, when the element has been found.

Also, I think you can make the function void as there is no need to return anything.

If you have any queries, feel free to ask in comments.