Binary Search Tree--code not working properly

Hello,
In this program I am using Binary search tree,I am supposed to insert some info about students.

The root of the tree saves the info that I insert. It lists (does display) the tree using in Order tree traversal, but when I try to trace the inserted info like to know what is saved in the root I find this works well and what goes to the right/left always gives Null so means it doesn't save in the right or in the left although it lists them in order. So it means also that I don't have a tree.

My code is given below,  please see and check what is the error. I am sure there won't be a bigger error but I am unable to find the error out.



The main class is TreeIterator. and the methods are in BinarySearchTree
class. It seems that the remove method is having the problem.
Thanks alot




--------------------------------------------------------------------------------

public class BinaryTree{
 
    private BinaryNode root;
   
    public BinaryTree(){root = null;}
   
    public BinaryTree(Comparable rootItem){
      root = new BinaryNode(rootItem);
    }
   
    public void printInOrder(){
      if(root != null) root.printInOrder();
    }
   
    public boolean isEmpty(){
      return root == null;
    }
   
    public void makeEmpty(){
      root = null;
    }
}

--------------------------------------------------------------------------------

public class BinarySearchTree implements SearchTree{
   
    protected BinaryNode root;
   
    public BinarySearchTree(){root = null;}

    public void insert(Comparable x) throws DuplicateItem{
      root = insert(x, root);
    }
   
    public void remove(Comparable x) throws ItemNotFound{
      root = remove(x, root);
    }
   
    public void removeMin() throws ItemNotFound{ root =
removeMin(root);}
   
    public Comparable findMin() throws ItemNotFound{return
findMin(root).element;}
   
    public Comparable findMax() throws ItemNotFound{return
findMax(root).element;}
   
    public Comparable find(Comparable x) throws ItemNotFound{ return
find(x, root).element;}    
   
    public boolean isEmpty(){return root == null;}
   
    public void makeEmpty(){root = null;}
   
    public BinaryNode insert(Comparable x, BinaryNode t) throws
DuplicateItem{
   
      if(t == null)
          t = new BinaryNode(x, null, null);
      else if(x.compares(t.element) > 0)
          t.left = insert(x,  t.left);
      else if(x.compares(t.element) < 0)
          t.right = insert(x, t.right);
      else throw new DuplicateItem("SearchTree insert");
      return t;
    }//insert
   
   
    public BinaryNode remove(Comparable x, BinaryNode t) throws
ItemNotFound{
      if(t == null) throw new ItemNotFound("SearchTree remove");
      if(x.compares(t.element) > 0 ) t.left = remove(x, t.left);
      else if(x.compares(t.element) < 0 )
          t.right = remove(x, t.right);
      else if(t.left != null && t.right != null){
          t.element = findMin(t.right).element;
          t.right = removeMin(t.right);
      }
      else //reroot t
          t = (t.left != null)? t.left : t.right;
      return t;
    }
   
    public BinaryNode find(Comparable x, BinaryNode t) throws
ItemNotFound{
      
      while(t != null)
          if(x.compares(t.element) > 0)
            t = t.left;
          else if(x.compares(t.element) < 0)
            t = t.right;
          else
            return t; //match
      throw new ItemNotFound("SearchTree find)");
    }
   
    public BinaryNode findMin(BinaryNode t) throws ItemNotFound{
      if(t == null) throw new ItemNotFound("SearchTree findMin");
      while(t.left != null)
          t = t.left;
          return t;
    }
   
    public BinaryNode findMax(BinaryNode t) throws ItemNotFound{
      if(t == null) throw new ItemNotFound("SearchTree findMax");
      while(t.right != null)
          t = t.right;
          return t;
    }
   
    public BinaryNode removeMin(BinaryNode t) throws ItemNotFound{
      if(t == null) throw new ItemNotFound("searchTree removeMin");
      if(t.left != null) t.left = removeMin(t.left);
      else t = t.right;
      return t;
    }
   
    public void printInOrder() {
      root.printInOrder();
    }
}

--------------------------------------------------------------------------------

public interface SearchTree{
 
    public BinaryNode insert(Comparable x, BinaryNode t) throws
DuplicateItem;
    public void insert(Comparable x) throws DuplicateItem;
    public BinaryNode remove(Comparable x, BinaryNode t) throws
ItemNotFound;
    public void remove(Comparable x)throws ItemNotFound;
   
}

--------------------------------------------------------------------------------

  public class InOrder extends TreeIterator{
      
      public InOrder(BinarySearchTree theTree){
          super(theTree);
          s = new StackAr();
          s.push(new StNode(t.root));
      }//InOrder
      
      public void first(){
          s.makeEmpty();
          if(t.root != null)
            s.push(new StNode(t.root));
          try{
            advance();
          }
          catch(ItemNotFound e){} //empty Tree
      }//first()
      
      protected Stack s;
      
      public void advance() throws ItemNotFound{
          if(s.isEmpty()){
            if(current == null)throw new ItemNotFound("INOrder advance");
            current = null;
            return;
          }//if
          StNode cnode;
          for(;;){
            try{
                cnode = (StNode) s.topAndPop();
            }//try
            catch(ItemNotFound e){
                return;      //cannot happen
            }//catch
            if(++cnode.timesPopped == 2){
                current = cnode.node;
                if(cnode.node.right != null)
                  s.push(new StNode(cnode.node.right));
                return;
            }//if
            //first time through
            s.push(cnode);
            if(cnode.node.left != null)
                s.push(new StNode(cnode.node.left));
          }//for
      }//advance()

}//class
   
class StNode{
    BinaryNode node;
    int timesPopped;
    StNode(BinaryNode n){node = n; timesPopped = 0;}
}
   
   

--------------------------------------------------------------------------------

public class DuplicateItem extends Exception{
   
    public DuplicateItem(String thrower){
      super(thrower);
      System.out.println(thrower);
    }
}


--------------------------------------------------------------------------------

public class BinaryNode{
   
    Comparable element;
    BinaryNode left;
    BinaryNode right;
     
    BinaryNode(){
      this(null);
    }
    BinaryNode(Comparable theElement){
      this(theElement, null, null);
    }
    BinaryNode(Comparable theElement, BinaryNode lt, BinaryNode rt){
      element = theElement; left = lt; right = rt;
    }
    void printInOrder(){
      if(left != null)
          left.printInOrder();      //left
          System.out.println(element);
          if(right != null)
            right.printInOrder();
    }

}//class


--------------------------------------------------------------------------------

 public class StackAr implements Stack{
   
    public StackAr(){
      theArray = new  Object[DEFAULT_CAPACITY];
      topOfStack = -1;
     }
   
    public void push ( Object x){
      if(topOfStack + 1 == theArray.length)
          doubleArray();
      theArray[++topOfStack] = x;
    }
   
    public boolean isEmpty(){
      return topOfStack == -1;
    }
    public void makeEmpty(){
      topOfStack = -1;
    }
   
    public  Object top() throws ItemNotFound{
      if(isEmpty()) throw new ItemNotFound("Stacj top");
      return theArray[topOfStack];
    }
    public void pop() throws ItemNotFound{
      if(isEmpty()) throw new ItemNotFound("Stack pop");
      topOfStack--;
    }
   
    public  Object topAndPop()throws ItemNotFound{
      if(isEmpty())  throw new ItemNotFound("Stack topAndPop");
      return theArray[topOfStack--];
    }
   
    private  Object[] theArray;
    private int topOfStack;
   
    static final int DEFAULT_CAPACITY = 10;
   
    private void doubleArray(){//?
    }
}


--------------------------------------------------------------------------------

public class Student implements Comparable {
   
    String sLName;
    String sIn;
    String userName;
    String pswrd;

    public void Student() {}
   
    public void Student(String theLastName, String theInitial, String
theUserName, String thePassword){
      sLName = theLastName;
      sIn = theInitial;
      userName = theUserName;
      pswrd = thePassword;
    }
   
    public String toString () {

      return (sLName + " " + sIn + " " + userName + " " + pswrd);
    }
   
    public int compares(Comparable s){
      
      Student stemp = (Student)this;
      if (stemp.sLName.compareTo(((Student)s).sLName) < 0) {
          return 1;
      }
      else if (stemp.sLName.compareTo(((Student)s).sLName) > 0) {
          return -1;
      }
      else if (stemp.sIn.compareTo(((Student)s).sIn) < 0) {
          return 1;
      }
          
      System.out.println ("from student lessThan student");
      return -1;  
    }
}

--------------------------------------------------------------------------------

public interface Stack{
    void push ( Object x);
    void pop()      throws ItemNotFound;
    Object top()    throws ItemNotFound;
    Object topAndPop() throws ItemNotFound;//to be changed to Underflow
    boolean isEmpty();
    void makeEmpty();
}



--------------------------------------------------------------------------------

public class TreeIterator {
    public static BinarySearchTree Tree;
    public static TreeIterator itr;
    public static BinaryNode b;
    public static Student s;
    public TreeIterator (BinarySearchTree theTree) {
      t = theTree;
      current = null;
      Tree = theTree;
    }//TreeIterator
   
    public static void main(String args[]) {
      System.out.println("hello");
      BinarySearchTree tmp = new BinarySearchTree();
      GUI temp = new GUI("hello");
      
    }
   
    final public boolean isValid(){
      return current != null;
    }
   
    final public Object retrieve() throws ItemNotFound{
      if(current == null)
          throw new ItemNotFound("TreeIterator retrieve");
      return current.element;
    }
   
    protected BinarySearchTree t;              //Tree
    protected BinaryNode current;      //Current position
    public BinaryNode root;
 
}//class

       
   
   




--------------------------------------------------------------------------------

public class ItemNotFound extends Exception{
   
    public ItemNotFound(String thrower){
      super(thrower);
      System.out.println(thrower);
    }
}

tparvaizAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

mbormannCommented:
why invent the wheel if u want to see excellent source code at
http://www.cs.fiu.edu/~weiss/dsj/code/
I think it closely models ur requirements.

Enjoy
0
tparvaizAuthor Commented:
thanks for your comments,
can you please point me( I mean in which chapter) exactly where can I find this code.

I am new in JAVA,thats why needed help.

Thanks any way
0
mbormannCommented:
am answering it now
download the file called as CodeWin95.zip for Win32

search at
Complete Bundle

    Windows 95 zip file
    Unix tar | compress file
    Unix tar
    Macintosh self-extracting archive, courtesy of Jeff Parker. Save the file and double click it.
    I have not tested this myself.

open
adspjava\Code\DataStructures\BinarySearchTree.java
and look at all other related files.

hope this helps u out
Regards
Amit
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.