#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

struct node 
{
    int data;
    struct node *left;
    struct node *right;
};

struct node* createNode(int value) 
{
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

struct node* insert(struct node *root, int value) 
{
    if (root == NULL) 
        return createNode(value);
    if (value < root->data) 
        root->left = insert(root->left, value);
	else if (value > root->data) 
        root->right = insert(root->right, value);
    return root;
}

struct node* search(struct node* root, int key) 
{
    if (root == NULL || root->data == key) 
        return root;
    
    if (key < root->data) 
        return search(root->left, key);
    
    return search(root->right, key);
}

void inorder(struct node *root) 
{
    if (root != NULL) 
	{
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

void main() 
{
    struct node *root = NULL;
    struct node *result = NULL;
    int n, i, value, key;

    clrscr();

    printf("--- BST Creation and Search Program ---\n");
    printf("Enter the number of nodes to insert: ");
    scanf("%d", &n);

    for (i = 0; i < n; i++) 
	{
        printf("Enter value for node %d: ", i + 1);
        scanf("%d", &value);
        root = insert(root, value);
    }

    printf("\nIn-order Traversal of BST: ");
    inorder(root);
    printf("\n\n");

    printf("Enter the key element to search: ");
    scanf("%d", &key);

    result = search(root, key);

    if (result != NULL) 
        printf("Success: Element %d found in the Binary Search Tree!\n", key);
	else 
        printf("Failure: Element %d NOT found in the Binary Search Tree.\n", key);

    getch();
}