package binaryTree;
import java.util.*;

public class BTree implements BTreeInterface
{
   private Object data;
   private BTree left, right;   
   
   
   // constructor
   public BTree(Object init, BTree lft, BTree rgt)
   {
      data = init;
      left = lft;
      right = rgt;
   }       

   public BTree(Object init)
   {
      data = init;
      left = right = null;
   }

   // get the data stored in the current node
   public Object getData( )   
   {
      return data;
   }

   public BTree getLeft( )
   {
      return left;                                               
   } 
   
   public BTree getRight( )
   {
      return right;                                               
   } 


   public void setData(Object obj)   
   {
      data = obj;
   }                                                               
   

   public void setLeft(BTree lft)
   {                    
      left = lft;
   }

   public void setRight(BTree rgt)
   {                    
      right = rgt;
   }  

   Vector v;
   public ListIterator preorderTraversal()
   {
      v = new Vector();
      preorder(this);
      return v.listIterator();
   }

   private void preorder(BTree bt)
   {
      if ( bt == null) {// empty case
	 return;
      } // end of if ()
 
      //nonempty case
      v.add(bt.getData());
      preorder(bt.getLeft());
      preorder(bt.getRight());
   }

   public int size()
   {
      return (sizeRecurse(this));
   }

   private int sizeRecurse(BTree b)
   {
      if ( b == null) {
	 return 0;
      } // end of if ()
      return (1 + sizeRecurse(b.getLeft())+sizeRecurse(b.getRight()));
   }

   public boolean isEmpty()
   {
      return(size() == 0);
   }

   public int numOfSubTrees()
   {
      int num = 0;
      if (right != null ) {
	 num++;
      } // end of if ()
      if ( left != null) {
	 num++;
      } // end of if ()
      return num;
   }
    
   public BTree removeRightmost()
   {
      if ( right == null) {
	 return left;
      } // end of if ()
      else {
	 right = right.removeRightmost();
	 return this;
      } // end of else
      
   }

   public BTree getRightmost()
   {
      if ( right == null) {
	 return this;
      } // end of if ()
      else {
	 
	 return right.getRightmost();
      } // end of else
      
   }

   public BTree removeLeftmost()
   {
      if ( left == null) {
	 return right;
      } // end of if ()
      else {
	 left = left.removeLeftmost();
	 return this;
      } // end of else
      
   }

   public BTree getLeftmost()
   {
      if ( left == null) {
	 return this;
      } // end of if ()
      else {
	 
	 return left.getLeftmost();
      } // end of else
      
   }
}