package trees;

class BSTree {
    private class Node {
        Comparable item;
        Node left;
        Node right;

        public Node(Comparable item) {
            this.item = item;
            left = null;
            right = null;
        }
    }

    private Node root;

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

    private Comparable find(Node t, Comparable x) {
        while (t != null)
            if (x.compareTo(t.item) < 0)
                t = t.left;
            else if (x.compareTo(t.item) > 0)
                t = t.right;
            else
                return t.item;
        return null;
    }

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

    private Comparable findMin(Node t) {
        if (t != null) {
            while (t.left != null)
                t = t.left;
            return t.item;
        }
        return null;
    }

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

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

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

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

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

    private Node remove(Node t, Comparable x) {
        if (t != null) {
            if (x.compareTo(t.item) < 0)
                t.left = remove(t.left, x);
            else if (x.compareTo(t.item) > 0)
                t.right = remove(t.right, x);
            else if (t.left == null)
                t = t.right;
            else if (t.right == null)
                t = t.left;
            else {
                t.item = findMin(t.right);
                t.right = remove(t.right, t.item);
            }
        }
        return t;
    }

    private void indent(int depth, Node node) {
        for (int i = 0; i < depth; i++)
            System.out.print("   ");
        System.out.println(node.item);
    }

    private void inorder() {
        inorder(root, 0);
    }

    private void inorder(Node node, int depth) {
        if (node != null) {
            inorder(node.right, depth + 1);
            indent(depth, node);
            inorder(node.left, depth + 1);
        }
    }

    public static BSTree makeTree(String[] items) {
        BSTree tree = new BSTree();
        for (int i = 0; i < items.length; i++)
            tree.insert(items[i]);
        return tree;
    }

    public static void testTree(BSTree tree) {
        System.out.println("INORDER");
        System.out.println();
        tree.inorder();
        System.out.println();
        System.out.println("find min: " + tree.findMin());
        System.out.println("find max: " + tree.findMax());
        System.out.println("find E: " + tree.find("E"));
        tree.remove("D");
        System.out.println("INORDER");
        System.out.println();
        tree.inorder();
        System.out.println();
    }

    public static void main(String[] args) {
        String[] rand = { "D", "H", "C", "A", "F", "E", "G", "B" };
        BSTree tree = makeTree(rand);
        testTree(tree);

        String[] alpha = { "A", "B", "C", "D", "E", "F", "G", "H" };
        tree = makeTree(alpha);
        testTree(tree);
    }
}