COSC4301				Program-6
				 BinarySearchTree Operations		Due: 11/13/2012 

 Tasks:  You are to modify the given program to
	1. Define a non-static (non-recursive) public method insertNonRec (int newElement) 
	   This method will insert a new node to the current BinarySearchTree to contain
	   the given new int element and will have the following heading:
	   	public void insertNonRec (int newElement) 
	2. Define and include a non-static public boolean method remove (int oldElement)
	   which will search the current BinarySearchTree to find and remove 
	   a node that contains the given oldElement and return 1
	   if successful or else return 0 (if the given oldElement is not found).
	   If found and removed, the binary tree needs to be restructured accordingly, 
	   Note that the existing method isInSubtree (int oldItem) searches the current BinarySearchTree 
	   for a node with the given int value of oldItem and returns that node if found or else a null node.
	   Also note that the above method sets two instance variables, parent (of TreeNode type) and 
	   parentLink (of int type) accordingly which the removal method may need and use.
	   This method for removal will have the following heading:
		public boolean remove (int oldElement)
	
	3. Define a copy constructor of a BinarySearchTree
	   This constructor will have the following heading:
		public BinarySearchTree (TreeNode root)
	   It will create a new BinarySearchTree that is a deep copy of an existing one which
	   the given TreeNode root specifies.
	4. Show the outputs of these new methods you define and include to the program
	   with some suitable heading messages. 
	   For details, please see the Input/Output requirements which immediately follow. 

 Input/output Requirements:

 1.  Use at least 12 input integers to construct a binarysearch tree.
 2.  Either the fifth input or the sixth input value must be 999 which will be removed later by your program 
      after a tree has been built entirely that contains all input values. 
 3.  Output integer values of all nodes of the completed tree in Inorder Sequence. 
      In this case, of course, integer node values must be output in ascending order, by definition of 
      binay search tree.
 4.  Output integer values of all nodes of the completed tree, one more time, in PreOrder sequence.
      For this, you can use a new recursive method just included here, showPreOrder (TreeNode currentRoot)
 5.  After your Copy Constructor has been invoked, output the Deep Copy of the tree in PostOrder sequence.
      For this, you need to define a method to be named showPostOrder just like showPreOrder.
 6.  After removing a node with 999, output the resulting tree in InOrder sequence.
 7.  Enjoy!!!
 
 Binary Search Tree property: 
 Binary tree is a tree in which every node has at most two child nodes (left child and right
 child) and hence a node can be represented by three fields: data, leftlink and rightlink.
 Binary Search Trees are special binary trees that satisfy a special property that each node
 is greater than any node in its Left subtree and is less than or equal to 
 any node in its Right subtree. This additional property results in an efficient search methods.
                  
/* Program to modify ////////////////////////////////////////////

public class BinarySearchTree
{
    private static class TreeNode	// an inner class of class BinarySearchTree, for binary trees
    {	// 3 private instance variables
	////////////////////////////////////////////////////////
        private int data;
        private TreeNode leftLink;
        private TreeNode rightLink;
	// One constructor for TreeNode
	///////////////////////////////////////////////////////
        public TreeNode(int newData, TreeNode newLeftLink,
                                        TreeNode newRightLink)
        {
             data = newData;
             leftLink = newLeftLink;
             rightLink = newRightLink;
        }
    } //End of TreeNode inner class

/**
 Class BinarySearchTree
 Class invariant: The tree satisfies the binary search tree storage rule
 such that every tree node is > than any node in its Left subtree and
 is <= than any node in its Right subtree...
                  
*/
public class BinarySearchTree
{
    private class TreeNode       // an inner class of class BinarySearchTree, for binary trees
    {	// 3 private instance variables
	////////////////////////////////////////////////////////
        private int data;
        private TreeNode leftLink;
        private TreeNode rightLink;
	// One constructor for TreeNode
	///////////////////////////////////////////////////////
        public TreeNode(int newData, TreeNode newLeftLink,
                                        TreeNode newRightLink)
        {
             data = newData;
             leftLink = newLeftLink;
             rightLink = newRightLink;
        }
    } //End of TreeNode inner class

    // Declaration of class BinarySearchTree begins here.
    ///////////////////////////////////////////
    // Just three instance variables.
    ///////////////////////////////////////////
    public  TreeNode root;
    private TreeNode parent; 	// parent node of a target node being sought
    private int parentLink;	// pointer number of a parent node being sought
			// 0: no parent, 1: left pointer pointing to the Left Child, 2: right pointer pointing to the Right child.
    //////////////////////////////////////////////////////////
    // One no-argument constructor for creating an empty binary tree.
    //////////////////////////////////////////////////////////
    public BinarySearchTree( )
    {
        root = parent = null;
        parentLink = 0; 		// no such pointer at the beginning
    }
    // One copy constructor to create one by making a deep copy of an existing tree given
    // by the root of the tree which is the lone parameter
    public BinarySearchTree (TreeNode rootNode)
    {
        parent = null;
 	parentLink = 0; 
	root = copyBST (rootNode);
    }
    ////////////////////////////////////////////////////////
    // Other methods follow
    /////////////////////////////////////////////////
    public void add(int newItem)
    {
        root = insertInSubtree(newItem, root);
    }
    /////////////////////////////////////////////////
    public void changeRoot (int newItem)
    // Just reset the root item to the given new item
    {
	root.data = newItem;
    }
    /////////////////////////////////////////////////
    public boolean remove (int oldItem)
    {
	// finds and removes a TreeNode containing the given oldItem and returns true
	// else (that is, if the given oldItem is not found), simply returns false
	/*
	When the TreeNode t containing given oldItem is found, 
	there are three cases to consider
	1. the TreeNode t has no child at all.
	2. it has only one child.
	3. it has both the two children
	Case-1: Simplest case
		It's parent's link is to set to null deleting the memory space for t.
	Case-2: A little involved.
		It's parent's link is to set to its lone child also deleting 
		the memory space for t.
	Case-3: We need a trick here.
		Intead of deleting the memory space of the TreeNode t itself, 
		we will find a replacement TreeNode r to replace t in contents and delete
		the memory space for r instead after copying the contents of r to t thereby
		saving the contents of r and deleting the contents of t, that is oldItem.
		This replacement TreeNode is going to be the last left child in the 
		binary tree rooted at the right of t as the replacement TreeNode must contain
		value immediately following the given oldItem.
	**/
        boolean success = true;
        TreeNode target, replaceNode, rightChild;
        parent = null;
        parentLink = 0;
        target = isInSubtree (oldItem);     // This is the node to remove.
        ///////////////////////////////////////////////////////////////////////////////////////////
        // The rest is your share to define and fill in, so it is omitted
    }		// end of boolean remove()
    /////////////////////////////////////////////////
    private TreeNode replace (TreeNode target)
    // finds and returns the last left child node of the right child of the target Node
    {   //	target must have a right child which has its own left child.
        	parent = target.rightLink;
	TreeNode current = parent.leftLink;
	while (current.leftLink != null)
	  {
	  parent = current;
	  current = current.leftLink;
	  }
	return current;
    }	//	end of replace()
    /////////////////////////////////////////////////   
    public TreeNode contains(int oldItem)
    {   
         return isInSubtree(oldItem);
    }
    /////////////////////////////////////////////////

    public void showElements( )
    {
        showInOrder(root);
    }
    /////////////////////////////////////////////////
    /**
    Inserts a new node that contains newItem into a binary search tree rooted
    at the given treeRoot.
    */
    public TreeNode insertInSubtree(int newItem, TreeNode treeRoot)
    {   if (treeRoot == null)
        {  treeRoot = new TreeNode (newItem, null, null);
           return treeRoot;
        }
        // else not done
        if (newItem < treeRoot.data)
        {    treeRoot.leftLink=insertInSubtree(newItem, treeRoot.leftLink);
             return treeRoot;
        }
        //      else newItem >= treeRoot.data
             treeRoot.rightLink=insertInSubtree(newItem, treeRoot.rightLink);
             return treeRoot;
    }   // end of insertInSubtree()
    ////////////////////////////////////////////////////////////////////////
    // 	This method finds and returns a TreeNode containing the given item along with its parent node and 
    // 	the link of the parent pointing to the TreeNode containing the given oldItem.    
    // 	parentLink=1: leftLink;  
    //                               =2: rightLink;  
    //                               =0: No parent and hence no parent's link.
    private TreeNode isInSubtree(int oldItem)
    {   TreeNode current;
         parent=null;    	//      assume no parent
         parentLink=0;   //      assume no parent
         current=root;
         if (current==null) return current;         // not found as binary tree is empty.
         while (current != null)
        {
                if (current.data == oldItem)
                   return current;
                if (current.data > oldItem)
                {  parent = current;
                   current =  current.leftLink;
                   parentLink=1;
                }
                else    // current.data < oldItem
                {  parent = current;
                   current = current.rightLink;
                   parentLink=2;
                }
        }
        return current;         // must be null as matching target not found.
    }   // 	end of isInSubtree()
    ///////////////////////////////////////////////

    private static void showInOrder (TreeNode treeRoot)
    { 
        // Uses inorder traversal.
        if (treeRoot != null)
        {
            showInOrder(treeRoot.leftLink);
            System.out.print(treeRoot.data + " ");
            showInOrder(treeRoot.rightLink);
        }	// else do nothing. Empty tree has nothing to display.
    }	// end of method showInOrder() 
    /////////////////////////////////////////////////////////////////////////////////////
    private static void showPreOrder (TreeNode currentRoot)
    {
	// print node values in preorder traversal.
	if (currentRoot == null) return;	// done in this case as the tree is empty
	// else there still is some node(s) left to be shown
  	System.out.print(currentRoot.data + " ");
	showPreOrder  (currentRoot.leftLink); 
	showPreOrder  (currentRoot.rightLink); 
    }	// end of method showPreOrder()
}	// end of class BinarySearchTree