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

   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;
   }
   
   /** An instance is the node of 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;
   }
}
}