package com.eruite.test;

class BinaryNode {
 Comparable element;

 BinaryNode left;

 BinaryNode right;

 BinaryNode(Comparable element) {
  this(element, null, null);
 }

 BinaryNode(Comparable element, BinaryNode left, BinaryNode right) {
  this.element = element;
  this.left = left;
  this.right = right;
 }
}

public class BinarySearchTree {
 private BinaryNode root;

 public BinarySearchTree() {
  root = null;
 }

 public void makeEmpty() {
  root = null;
 }

 public boolean isEmpty() {
  return root == null;
 }

 public Comparable find(Comparable x) {
  return elementAt(find(x, root));
 }

 public Comparable findMin() {
  return elementAt(findMin(root));
 }

 public Comparable findMax() {
  return elementAt(findMax(root));
 }

 public void insert(Comparable x) {
  root = insert(x, root);
 }

 public void remove(Comparable x) {
  root = remove(x, root);
 }

 public void printTree() {
  if (isEmpty())
   System.out.println("Empty Tree");
  else
   printTree(root);
 }

 private Comparable elementAt(BinaryNode t) {
  return t == null ? null : t.element;
 }

 private BinaryNode find(Comparable x, BinaryNode t) {
  if (t == null)
   return null;
  if (x.compareTo(t.element) < 0)
   return find(x, t.left);
  else if (x.compareTo(t.element) > 0)
   return find(x, t.right);
  else
   return t;
 }

 private BinaryNode findMin(BinaryNode t) {
  if (t == null)
   return null;
  else if (t.left == null)
   return t;
  return findMin(t.left);
 }

 private BinaryNode findMax(BinaryNode t) {
  if (t != null) {
   while (t.right != null)
    t = t.right;
  }
  return t;
 }

 private BinaryNode insert(Comparable x, BinaryNode t) {
  if (t == null)
   t = new BinaryNode(x);
  else if (x.compareTo(t.element) < 0)
   t.left = insert(x, t.left);
  else if (x.compareTo(t.element) > 0)
   t.right = insert(x, t.right);
  else
   ;
  return t;
 }

 private BinaryNode remove(Comparable x, BinaryNode t) {
  if (t == null)
   return t;
  if (x.compareTo(t.element) < 0)
   t.left = remove(x, t.left);
  else if (x.compareTo(t.element) > 0)
   t.right = remove(x, t.right);
  else if (t.left != null && t.right != null) {
   t.element = findMin(t.right).element;
   t.right = remove(x, t.right);
  } else
   t = (t.left != null) ? t.left : t.right;
  return t;
 }

 private void printTree(BinaryNode t) {
  if (t != null) {
   printTree(t.left);
   System.out.print(t.element);
   printTree(t.right);
  }
 }

 public static void main(String[] args) {
  BinarySearchTree bst = new BinarySearchTree();
  bst.insert(new Integer(1));
  bst.insert(new Integer(2));
  bst.insert(new Integer(3));
  bst.insert(new Integer(4));
  bst.insert(new Integer(5));
  bst.insert(new Integer(6));
  Comparable c = bst.find(new Integer(6));
  if (c != null)
   System.out.print(c);
  else
   System.out.println("not exist");
 }
}