Steps:

Create a Node structure that has a left and right pointer to point to the left and right child nodes.

Create a BST using recursion. While insertion the value is checked with the root value. If the value is lesser than the root we move to the left subtree else to the right subtree. This continues until an empty place is found to place the new node.

The display function displays the nodes of the tree in an inorder fashion this is left root right.

The search function returns NULL if no such target is found else returns the node with the target value.

#include<iostream>

using namespace std;

struct Node{
string val;
struct Node *left;
struct Node *right;
};

//method to insert new nodes
struct Node* insertNode(struct Node *root,string val)
{
if(root==NULL)
{
//create a new node
struct Node *newNode=new Node();
newNode->val=val;
newNode->left=newNode->right=NULL;
return newNode;
}

if(val<root->val)
root->left=insertNode(root->left,val);
else
root->right=insertNode(root->right,val);

return root;
}

//method to display the tree
void display(struct Node *root)
{
//perform inorder traversal
if(root!=NULL)
{
display(root->left);
cout<<root->val<<" ";
display(root->right);
}
}

//method to search the tree
struct Node* searchNode(struct Node *root,string val)
{
if(root==NULL || root->val==val)
{
return root;
}
if(root->val<val)
{
return searchNode(root->right,val);
}
return searchNode(root->left,val);
}

int main()
{
struct Node *root=NULL,*node;

//display the menu
int choice;
string val;

while(1)
{
cout<<"1. Insert Node"<<endl;
cout<<"2. Display Nodes"<<endl;
cout<<"3. Search Node"<<endl;
cout<<"4. Exit"<<endl;
cout<<"Enter choice: ";
cin>>choice;

fflush(stdin);
switch(choice)
{
case 1: cout<<"Enter string: ";
getline(cin,val);
root=insertNode(root,val);
cout<<val<<" added"<<endl;
break;
case 2: cout<<"Inorder traversal of tree: ";
display(root);
cout<<endl;
break;
case 3: cout<<"Enter string: ";
getline(cin,val);
node=searchNode(root,val);
if(node==NULL)
{
cout<<val<<" not found."<<endl;
}
else{
cout<<val<<" found."<<endl;
}
break;
case 4: exit(0);
default:cout<<"Wrong choice"<<endl;
}
cout<<endl;
}
}