import java.io.*;

// Represents a single node in the BST
class BSTNode {
    int data;
    BSTNode left, right;

    public BSTNode(int value) {
        data = value;
        left = null;   // No left child initially
        right = null;  // No right child initially
    }
}

// Binary Search Tree with insert, search, and traversal operations
class BST {
    BSTNode root;  // Root node of the tree

    // Public method to insert a value into the BST
    public void insert(int value) {
        if (root == null) {
            root = new BSTNode(value);  // First insertion becomes root
        } else {
            insertRecursive(root, value);
        }
    }

    // Recursively finds the correct position and inserts
    private void insertRecursive(BSTNode current, int value) {
        if (current.data == value) {
            System.out.println("Value already present in tree");
            return;
        } else if (value < current.data) {
            // Go left if value is smaller
            if (current.left == null) {
                current.left = new BSTNode(value);
            } else {
                insertRecursive(current.left, value);
            }
        } else {
            // Go right if value is larger
            if (current.right == null) {
                current.right = new BSTNode(value);
            } else {
                insertRecursive(current.right, value);
            }
        }
    }

    // Inorder traversal: Left → Root → Right (produces sorted output)
    public void printInorder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        inorderRecursive(root);
        System.out.println();
    }

    private void inorderRecursive(BSTNode node) {
        if (node != null) {
            inorderRecursive(node.left);
            System.out.print(node.data + " ");
            inorderRecursive(node.right);
        }
    }

    // Preorder traversal: Root → Left → Right
    public void printPreorder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        preorderRecursive(root);
        System.out.println();
    }

    private void preorderRecursive(BSTNode node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preorderRecursive(node.left);
            preorderRecursive(node.right);
        }
    }

    // Postorder traversal: Left → Right → Root
    public void printPostorder() {
        if (root == null) {
            System.out.println("Tree is empty");
            return;
        }
        postorderRecursive(root);
        System.out.println();
    }

    private void postorderRecursive(BSTNode node) {
        if (node != null) {
            postorderRecursive(node.left);
            postorderRecursive(node.right);
            System.out.print(node.data + " ");
        }
    }

    // Search for a value in the BST
    public void search(int value) {
        searchRecursive(root, value);
    }

    private void searchRecursive(BSTNode node, int value) {
        if (node == null) {
            System.out.println("Data not found");
            return;
        }
        if (node.data == value) {
            System.out.println("Data found");
        } else if (value < node.data) {
            searchRecursive(node.left, value);   // Search left subtree
        } else {
            searchRecursive(node.right, value);  // Search right subtree
        }
    }
}

public class BSTDemo {
    public static void main(String[] args) throws IOException {
        BST tree = new BST();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int choice;

        do {
            System.out.println();
            System.out.println("--- Binary Search Tree Menu ---");
            System.out.println("1. Insert element");
            System.out.println("2. Display Inorder (sorted)");
            System.out.println("3. Display Preorder");
            System.out.println("4. Display Postorder");
            System.out.println("5. Search element");
            System.out.println("6. Exit");
            System.out.print("Enter option: ");
            choice = Integer.parseInt(reader.readLine());

            switch (choice) {
                case 1:
                    System.out.print("Enter element to insert: ");
                    int insertValue = Integer.parseInt(reader.readLine());
                    tree.insert(insertValue);
                    break;
                case 2:
                    System.out.print("Inorder: ");
                    tree.printInorder();
                    break;
                case 3:
                    System.out.print("Preorder: ");
                    tree.printPreorder();
                    break;
                case 4:
                    System.out.print("Postorder: ");
                    tree.printPostorder();
                    break;
                case 5:
                    System.out.print("Enter element to search: ");
                    int searchValue = Integer.parseInt(reader.readLine());
                    tree.search(searchValue);
                    break;
                case 6:
                    System.out.println("Exiting...");
                    break;
                default:
                    System.out.println("Invalid option");
            }
        } while (choice != 6);
    }
}