public class BinaryTree {

  protected BinaryTreeNode root;


  /**
   * The default constructor: creates an empty binary search tree
   */
  public BinaryTree()
  {
    root = null;
  }


  /**
   * Inserts a value into the proper position of a binary search tree.
   *  @param value to be inserted into the binary search tree
   */
  public void insert(Comparable data)
  {
    if (null == data)
      return;
    
    root = insert(root, data);
  }


  /**
   * This is a helper method -- no further description available
  */
  protected BinaryTreeNode insert(BinaryTreeNode root, Comparable value)
  {
    if (null == root)
      return new BinaryTreeNode(value);
    
    if (value.compareTo(root.getValue()) == 0)
      return root;
    
    if (value.compareTo(root.getValue()) < 0)
      root.setLeft ( insert(root.getLeft(), value) );
    else
      root.setRight ( insert(root.getRight(), value) );
    
    return root;
  }


  /**
   * This is a helper method -- no further description available
   */
  protected String niceTreeString (BinaryTreeNode t, String indent)
  {
    return (t==null?"":(t.getRight()==null?"":niceTreeString(t.getRight(),"  "+indent)) +
           indent+t.getValue()+System.getProperty("line.separator")+
           (t.getLeft()==null?"":niceTreeString(t.getLeft(),"  "+indent)));
  } 


  /**
   * Provides a nice string represention of a BinaryTree. 
   * <p>
   * Students should not concern themselves with how it works -- an 
   * understanding of this is not important to this exam.
   */
  public String toString()
  {
    if (root == null)
      return "(empty tree)";
    else
      return niceTreeString(root,"  ");
  }

  
  protected class BinaryTreeNode {

     //Public instance variables: no need for getters/settors
     
     /**
      *  Note <code>final</code> access modifier: cannot be changed!
      *  Also, there is no setter for <code>value</code>.
     */
     public final Comparable value;
     
     public BinaryTreeNode left, right;


     /**
     *  Constructor builds the BinaryTreeNode with the supplied parameter;
     *  it has empty subtrees.
     *  @param value to store in this node
     */
     public BinaryTreeNode(Comparable value)
     {
        this.value = value;
        this.left = this.right = null;
     }


     /**
     *  Constructor builds the BinaryTreeNode with the supplied parameters.
     *  @param value to store in this node
     *  @param left  must refer to its left subtree
     *  @param right must refer to its right subtree
     */
     public BinaryTreeNode(Comparable value, BinaryTreeNode left, BinaryTreeNode right)
     {
        this.value = value;
        this.left  = left;
        this.right = right;
     }

     
     
     //////////
     //
     //  Getters and Setters for those students who want to use them.
     //
     //////////
     
     
     /**
     *  Returns reference to the left child, or null, if none.
     *  @return reference to left child
     */
     public BinaryTreeNode getLeft()
     {
        return left;
     }


     /**
     *  Returns reference to the right child, or null, if none.
     *  @return reference to right child
     */
     public BinaryTreeNode getRight()
     {
        return right;
     }


     /**
     *  Sets the left-child reference of this object to the parameter object.
     *  @param newLeftChild which is an object of the class BinaryTreeNode
     */
     public void setLeft(BinaryTreeNode newLeftChild)
     {
       left = newLeftChild;
     }


     /**
     *  Sets the right-child reference of this object to the parameter object.
     *  @param newRightChild which is an object of the class BinaryTreeNode
     */
     public void setRight(BinaryTreeNode newRightChild)
     {
       right = newRightChild;
     }


     /**
     *  Returns reference to the value of the object.
     *  @return reference to the value
     */

     public Comparable getValue()
     {
        return value;
     }


     /**
     *  Returns string representation of the object
     *  @return String reference
     */
     public String toString()
     {
        return value.toString();
     }
  }
}