// TreeNode
public class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  public TreeNode(int data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

// BinarySearchTree
public class BinarySearchTree {
  private TreeNode root;

  public BinarySearchTree() {
    this.root = null;
  }

  // 삽입 연산
  public void insert(int data) {
    root = insertRec(root, data);
  }

  private TreeNode insertRec(TreeNode root, int data) {
    if (root == null) {
      root = new TreeNode(data);
      return root;
    }

    if (data < root.data) {
      root.left = insertRec(root.left, data);
    } else if (data > root.data) {
      root.right = insertRec(root.right, data);
    }
    return root;
  }

  // 탐색 연산
  public boolean search(int data) {
    return searchRec(root, data);
  }

  private boolean searchRec(TreeNode root, int data) {
    if (root == null) {
      return false;
    }

    if (root.data == data) {
      return true;
    }

    if (data < root.data) {
      return searchRec(root.left, data);
    } else {
      return searchRec(root.right, data);
    }
  }

  // 중위 순회(Inorder Traversal)
  public void inorder() {
    inorderRec(root);
  }

  private void inorderRec(TreeNode root) {
    if (root != null) {
      inorderRec(root.left);
      System.out.print(root.data + " ");
      inorderRec(root.right);
    }
  }
}

// Main
public class Main {

  public static void main(String[] args) {
    BinarySearchTree bst = new BinarySearchTree();

    bst.insert(50);
    bst.insert(30);
    bst.insert(20);
    bst.insert(40);
    bst.insert(70);
    bst.insert(60);
    bst.insert(80);

    System.out.println("Inorder traversal of the BST:");
    bst.inorder(); // 출력: 20 30 40 50 60 70 80

    System.out.println("\nSearch for 40: " + bst.search(40)); // 출력: true
    System.out.println("Search for 90: " + bst.search(90)); // 출력: false
  }
}