using namespace std;
class node
{
public:
int data;
node *left;
node *right;
};
node *root;
node *getnewnode(int );
node *insert(node *, int);
bool search(node *, int);
void preorder(node *);
int main()
{
root = NULL;
int option, num;
do
{
cout << "1:Insert node:" << endl;
cout << "2:Search Any given node:" << endl;
cout << "3:Preorder Traversal:" << endl;
cout << "Enter your option: " << endl;
cin >> option;
switch (option)
{
case 1:
cout << "Enter the data: " << endl;
cin >> num;
root = insert(root, num);
cout << "Node Inserted successfully" << endl;
break;
case 2:
cout << "Search the data now:" << endl;
cin >> num;
if (search(root, num) == true)
cout << "Found\n";
else
cout << "Not Found\n";
break;
case 3:
cout << "Preorder:" << endl;
preorder(root);
break;
}
} while (option != 4);
return 0;
}
node *getnewnode(int num)
{
node *newnode = new node();
newnode->data = num;
newnode->left = newnode->right = NULL;
return newnode;
}
// To insert data in BST, returns address of root node
node *insert(node *root, int num)
{
if (root == NULL)
{ // empty tree
root = getnewnode(num);
}
// if data to be inserted is lesser, insert in left subtree.
else if (num <= root->data)
{
root->left = insert(root->left, num);
}
// else, insert in right subtree.
else
{
root->right = insert(root->right, num);
}
return root;
}
//To search an element in BST, returns true if element is found
bool search(node *root, int num)
{
if (root == NULL)
{
return false;
}
else if (root->data == num)
{
return true;
}
else if (num <= root->data)
{
return search(root->left, num);
}
else
{
return search(root->right, num);
}
}
void preorder(node *root)
{
if (root = NULL)
return;
cout << root->data << " "; //Printf root->data
preorder(root->left); //go to left sub tree
preorder(root->right); //go to right sub tree
}