/** A binary search tree on Strings. */
public class BST {

    /** An node in a tree. */
    class TreeNode<T> {
        private T datum;
        private TreeNode<T> left, right;

        /** Constructor: a node with value d and empty left- and right subtrees. */
        public TreeNode(T d) {
            datum= d;
            left= null;
            right= null;
        }
    }
    
    TreeNode<String> root; // The root of the BST. null if empty

    /** Constructor. An empty tree */
    public BST() {
        root= null;
    }

    /** Insert s into this tree. Nothing happens if s is already in the BST. */
    public void insert(String s) {
        root= insert(s, root);
    }

    /** Precondition: node is a possibly empty BST.
     * Add s to node (if it is not in the BST) and
     * return the root of the new BST. */
    private TreeNode<String> insert(String s, TreeNode<String> node) {
        if (node == null) return new TreeNode<String>(s);
        int compare= s.compareTo(node.datum);
        if (compare < 0) node.left= insert(s, node.left);
        else if (compare > 0) node.right= insert(s, node.right);
        return node;
    }

    /** Print the contents of the BST in dictionary order.  */
    public void show() {
        show(root);
        System.out.println();
    }

    /** Print the contents of BST node in dictionary order, on one line. */
    private void show(TreeNode<String> node) {
        if (node == null) return;
        show(node.left);
        System.out.print(node.datum + " ");
        show(node.right);
    }

    /** Return a representation of this BST, one line per node. */
    public String toString() {
        return toString("", root);
    }

    /** Print BST tree node, one line per node, preceded by prefix.
     * Prefix is changed to that the output looks like a tree without lines.
     with up being right and down being left.*/
    private String toString(String prefix, TreeNode<String> node) {
        if (node == null) return "";
        String string= prefix + node.datum.toString();
        if (node.right != null)
            string = toString("    " + prefix, node.right) + "\n" + string;
        if (node.left != null)
            string = string + "\n" + toString("    " + prefix, node.left);
        return string;
    }
}