/*BS TREE CLASS
  Giri Gopalan
  2/ 17/ 05 */
public class tree
 {
  private node root; // root of tree

  public tree ()
   {
    root = null;    // constructor initializes empty tree;
   }
  public boolean check(Comparable obj)
/* PURPOSE: to check if a certain object is contained in the tree
   METHOD: do a binary search to check if the item is in the tree
   INPUT: obj, item to be found
   OUTPUT: true if item is found, false if not */
   {
    node cur = root;   // node to scan through tree
    if (root != null)  
     {
      while(cur != null) // terminating case: scan node is null
       {
        if (obj.compareTo(cur.data) == 0) // if item found, return true
         return true;
        else if (obj.compareTo(cur.data) < 0) //go left if obj less than current
         cur = cur.left;
        else                                  // otherwise go right
         cur = cur.right;
       }
     }
     return false;
   }
  public void insert(Comparable obj)
/* PURPOSE: to insert an object in the tree
   METHOD: do a binary search to find appropriate place to insert
   INPUT: obj, item to be inserted
   OUTPUT: none */
   {
    node prev = null, cur = root; //current node and previous node to scan the tree
    boolean last = false; //flag: true if cur <-- rt ref., false if cur <-- left
    if (root == null) // case 1: inserting into an empty tree
     root = new node (obj, null, null);
    else    // case 2: inserting anywhere else
     {
      while(cur != null) //scan through through tree until current node is null
       {
        prev = cur;
        if (obj.compareTo(cur.data) < 0) //follow left ref. if insertee is 
         {cur = cur.left;last = true;}         //smaller than cur node 
        else
         {cur = cur.right;last= false;}  //follow right ref. otherwise       
       }
      if (last == true)
       prev.left = new node(obj, null, null); 
      else
       prev.right = new node(obj, null, null);
     }
   }
/* PURPOSE: to delete an object from the tree
   METHOD: first find item in the tree, then go through several cases to delete
   INPUT: obj, item to be deleted
   OUTPUT: none */
  public void delete(Comparable obj)
   {
    node prev = null, cur = root, temp; //scan variables
    boolean last = false;  /// flag: true if current came from left, false if rt.
    while (obj.compareTo(cur.data) != 0) // find item in tree with scan vars
     {
      prev = cur;
      if (obj.compareTo(cur.data) < 0)
       {cur = cur.left; last = true;}
      else
       {cur = cur.right; last = false;}
     }
     if (cur.right == null && cur.left == null) //case1: node has no children
      {
       if (cur == root)
        root = null;
       else if (last == true)
        prev.left = null;
       else
        prev.right = null;
      }
     else if (cur.right == null) //case2: node has only right child
      {
       if (cur == root)
        {root.data = cur.left.data; root.left = null;} 
       else if (last == true)
        prev.left = cur.left;
       else
        prev.right = cur.left;
      }
     else if (cur.left == null) //case 3: node has only left child
      {
       if (cur == root)
        {root.data = cur.right.data; root.right = null;} 
       else if (last == true)
        prev.left = cur.right;
       else
        prev.right = cur.right;
      }
     else         //case 4: node has two children
      {
       temp = cur.right; prev = cur; last = false;
       while (temp.left != null)
        {prev = temp; temp = temp.left; last = true;}
       if (last == true)
        prev.left = null;
       else
        prev.right = null;
       cur.data = temp.data;
      }     
   }          
/* PURPOSE: to print contents of tree in order
   METHOD: use an object that implements iterator to do in order traversal
   INPUT: none
   OUTPUT: none */
  public void print()
   {
    traverse t = new traverse(root); // iterator object
    while(t.hasNext() == true)     //keep printing until there are no more nodes 
     System.out.println(t.next());                   //to process
   }
 }