class BST<T extends Comparable<? super T>> {
    private class Node {
        T data;
        Node left, right;
        public Node(T val) { data = val; left = right = null; }
        T getData() { return data; }
        public int compareTo(Node n) {
            return this.getData().compareTo(n.getData());
        }
        public String toString() { return data.toString(); }
    }
    
    private Node root = null;
    public BST() {}
    
    public boolean find(T val) {
        Node cur = root;
        while (cur != null) {
            int comp = val.compareTo(cur.data);
            if (comp < 0) cur = cur.left;
            else if (comp > 0) cur = cur.right;
            else return true;
        }
        return false;
    }
    
    public boolean insert(T val) {
        Node cur, parent;
        Node n = new Node(val);
        if (root == null) root = n;
        else {
            cur = root;
            while (true) {
                parent = cur;
                int comp = val.compareTo(cur.data);
                if (comp < 0) {
                    cur = cur.left;
                    if (cur == null) { parent.left = n; break; }
                } else if (comp > 0) {
                    cur = cur.right;
                    if (cur == null) { parent.right = n; break; }
                } else {
                    // if we ever want to increment a counter
                    // to account for duplicates, here is
                    // where we would replace code to do it
                    cur = cur.left;
                    if (cur == null) { parent.left = n; break; }
                }
            }
        }
        return true;
    }
    
    public boolean delete(T val) {
        Node cur = root;
        Node parent = root;
        boolean isLeftChild = true;
        
        if (root == null) return false;
        
        // search for node
        while (val.compareTo(cur.data) != 0) {
            parent = cur;
            if (val.compareTo(cur.data) < 0) {
                cur = cur.left;
                isLeftChild = true;
            } else {
                cur = cur.right;
                isLeftChild = false;
            }
            if (cur == null) return false;
        }
        
        // here is where we would put code to
        // check and decrement a count and return
        // instead of just deleting the node (if
        // we had a count in the node)
        
        // do delete for node with no children
        if ((cur.left == null) && (cur.right == null)) {
            if (cur == root) root = null;
            else if (isLeftChild) parent.left = null;
            else parent.right = null;
        } else if (cur.right == null) {
            // do delete for node with one left child
            if (cur == root) root = cur.left;
            else if (isLeftChild) parent.left = cur.left;
            else parent.right = cur.left;
        } else if (cur.left == null) {
            // do delete for node with one right child
            if (cur == root) root = cur.right;
            else if (isLeftChild) parent.left = cur.right;
            else parent.right = cur.right;
        } else {
            // do delete for node with two children
            Node suc = cur;
            Node sucParent = cur;
            Node delNode = cur;
            
            Node tmp = delNode.right;
            while (tmp != null) {
                sucParent = suc;
                suc = tmp;
                tmp = tmp.left;
            }
            if (suc != delNode.right) {
                sucParent.left = suc.right;
                suc.right = delNode.right;
            }
            if (cur == root) root = suc;
            else if (isLeftChild) parent.left = suc;
            else parent.right = suc;
            
            suc.left = cur.left;
        }
        return true;
    }
    
    public void inorder() {
        inorder(root); System.out.println();
    }
    
    public void preorder() {
        preorder(root); System.out.println();
    }
    
    public void postorder() {
        postorder(root); System.out.println();
    }
    
    public void inorder(Node n) {
        if (n != null) {
            inorder(n.left);
            System.out.println(n);
            inorder(n.right);
        }
    }
    
    public void preorder(Node n) {
        if (n != null) {
            System.out.println(n);
            preorder(n.left);
            preorder(n.right);
        }
    }
    
    public void postorder(Node n) {
        if (n != null) {
            postorder(n.left);
            postorder(n.right);
            System.out.println(n);
        }
    }
}