/* 15-200 Assignment 8
 * Name: 
 * Andrew ID: 
 * Section: 
 */

/*
 * This class implements a binary search tree.  It stores a reference to
 * the root node as its data
 *
 * This class also contains a private subclass which is used to represent
 * the internal nodes of the tree
 */
public class BinarySearchTree
{
  /*
   * class to represent an internal node of the binary tree
   */
  private class BinaryNode
  {
    /*
     * Declare instance variables for the BinaryNode class here
     * Hint: The user's record should be of type Comparable
     */


    /*
     * A constructor for the BinaryNode class, takes in only the data
     * to be stored and sets the left child and the right child to
     * null
     */
    public BinaryNode(Comparable data)
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Another constructor for the BinaryNode class, takes in the data
     * to be stored, a reference to the left child, and a reference to
     * the right child
     */
    public BinaryNode(Comparable data, BinaryNode left, BinaryNode right)
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Returns a reference to the user's record
     */
    private Comparable getData()
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Returns a reference to the left child
     */
    private BinaryNode getLeft()
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Returns a reference to the right child
     */
    private BinaryNode getRight()
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Changes the left child of the node
     */
    private void setLeft(BinaryNode left)
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Changes the right child of the node
     */
    private void setRight(BinaryNode right)
    {
      /*
       * Insert you code here
       */
    }


    /*
     * Returns true if this node has no children,
     * false otherwise
     */
    private boolean isLeaf()
    {
      /*
       * Insert you code here
       */
    }
  }


  /*
   * declare instance variables for the BinarySearchTree class here
   */
   

  /*
   * Constructor for the BinarySearchTree class
   */
  public BinarySearchTree()
  {
    /*
     * Insert you code here
     */
  }


  /*
   * Inserts a new record into the right place within tree.
   * It should simply check parameters and wrap the recursive method.
   */
  public void insert(Comparable data)
  {
    /*
     * Insert you code here
     */
  }

  /*
   * Recursive method which inserts a new element
   * into the tree. The tree must stay ordered after
   * the new element has been added
   */
  private BinaryNode insert(BinaryNode root, Comparable data)
  {
    /*
     * Insert you code here
     */
  } 


  /*
   * User method for finding an element in the tree.
   * It returns null if the data isn't found, or a reference
   * back to the data if it is found.
   */
  public Comparable find(Comparable data)
  {
    /*
     * Insert you code here
     */
  }
  
  /*
   * Recursive method which traverses the tree until
   * it either finds the data it is looking for, in which
   * case it returns a reference to that data, or hits the
   * end of a path, in which case it returns null.
   */
  private Comparable find(BinaryNode root, Comparable data)
  {
    /*
     * Insert you code here
     */
  }


  /*
   * This should check paramters and then call the recursive method
   * to handle the delete
   */
  public void delete(Comparable data)
  {
    /*
     * Insert you code here
     */
  }

  /*
   * Recursive method which removes an element
   * from the tree. The tree must stay ordered after
   * the element has been removed
   */
  private BinaryNode delete(BinaryNode root, Comparable data)
  {
    /*
     * Insert you code here
     */
  }

  /*
   * Hint: You may want to think about writing one or more helper
   * methods for your delete. This would be a good place to put
   * them, if you do.
   */

  /*
   * This should print the content of the database in sorted order.
   * It should really be a wrapper for the recursive method below.
   */
  public void printInOrder()
  {
    /*
     * Insert you code here
     */
  }

  /*
   * Recursive method which performs an in-order
   * traversal of the tree. It should display the
   * tree's contents on the console
   */
  private void printInOrder(BinaryNode root)
  {
    /*
     * Insert you code here
     */
  }

  /*
   * This should print the content of the database in reverse sorted order.
   * In other words, in exactly the opposite order as printInOrder() above.
   * It should really be a wrapper for the recursive method below.
   */
  public void printInOrderBackwards()
  {
    /*
     * Insert you code here
     */
  }

  /*
   * Recursive method which performs the reverse of an in-order
   * traversal of the tree. It should display the
   * tree's contents on the console
   */
  private void printInOrderBackwards(BinaryNode root)
  {
    /*
     * Insert you code here
     */
  }
}
}