package coahranm.bst;

/**
 * A simple Binary Search Tree (BST) that stores integer keys.
 * (See BSTNode.java in this package.)
 *
 * @author Marge Coahran
 * @version September 8, 2006
 */
public class BST {
    /* fields ------------------------------------------------ */
	/** A reference to the root node of the BST */
    private BSTNode root;

    /* constructors ------------------------------------------ */
    /** Constructs an empty BST */
    public BST() {root = null;}

    /* public methods ---------------------------------------- */
    /**
     * Creates a string representation of the tree, using 
     * a pre-order tree traversal. (Useful for testing/debugging.)
     * 
     * @return 
     *   The generated string
     */
    public String toString() {
    	return toString(root, 0);
    }//toString()

    /**
     * Insert a key into the BST. Does nothing if the key is 
     * already in the tree.
     * 
     * @param key
     *   the key to insert
     * @post
     *   The BST contains key.
     */
    public void insert(int key) {
    	root = insert(key, root);
    }//insert(int key)

    /**
     * Remove a key from the BST. Does nothing if the key is 
     * not in the tree.
     * 
     * @param key
     *   the key to remove
     * @post
     *   The BST does not contain key.
     */
    public void remove(int key) {
    	root = remove(key, root);
    }//remove(int key)

    /**
     * Find and return the minimum key in the tree. (This method
     * is used primarily to test the corresponding private method.)
     * 
     * @return 
     *   the minimum key in the tee
     * @pre
     *   The BST is not empty.
     * @post
     *   The BST is unchanged.
     */
    public int minKey() {
    	/* this will crash if tree is empty (ie, if root==null)
    	 *  should throw an exception, but for now this is ok. */
    	return findMin(root).key;
    }//minKey(void)


    /* private methods --------------------------------------- */

    /**
     * Creates a string representation of the subtree rooted
     * at node, via a pre-order tree traversal.
     * 
     * @param node
     *   The root node of the subtree to represent
     * @param depth
     *   Node's depth within the full BST. (Used to produce 
     *   indentation that helps to visualize the tree.)
     * @return 
     *   The generated string
     */
    private static String toString(BSTNode node, int depth) {
    	if (node == null) {
    		return "";
    	}
    	else {
    		String str = new String();

    		//prepend spaces to illustrate node depth
    		for (int i=0; i<depth; i++)
    			str = str + " ";          //very inefficient!

    		//pre-order traversal
    		str = str + node.key + "\n";
    		str = str + toString(node.left, depth+1);
    		str = str + toString(node.right, depth+1);

    		return str;
    	}
    }

    /**
     * Insert key into subtree rooted at node. (Providing this
     * method separately from the public method insert allows
     * us to encapsulate the internal structure of the BST and
     * to use a recursive implementation. Returning a reference
     * to the updated subtree is important when the input node
     * is null and the returned node is not.)
     * 
     * @param key
     *   The key to insert
     * @param node
     *   The root of the subtree in which to insert key
     * @return 
     *   A reference to the root of an updated subtree.
     * @post
     *   The subtree rooted at the returned node contains key.
     */
    private static BSTNode insert(int key, BSTNode node) {
    	//if node is an empty tree... 
    	if (node == null)
    		//construct and return a node containing key
    		return new BSTNode(key);

    	//if subtree rooted at node is not empty...
    	if (key == node.key) {
    		//key already exists in tree: don't insert it
    	}
    	else if (key < node.key) {
    		//insert key into left subtree of node
    		node.left = insert(key, node.left);
    	}
    	else {
    		//insert key into right subtree of node
    		node.right = insert(key, node.right);
    	}
    	//return a reference to (updated subtree rooted at) node
    	return node;
    }//insert(int key, BSTNode node)

    /**
     * Remove key from subtree rooted at node. (Providing this
     * method separately from the public method remove allows
     * us to encapsulate the internal structure of the BST and
     * to use a recursive implementation. Returning a reference
     * to the updated subtree is important when the input node
     * itself is removed from the tree.)
     * 
     * @param key
     *   The key to remove
     * @param node
     *   The root of the subtree from which to remove key
     * @return 
     *   A reference to the root of an updated subtree.
     * @post
     *   The subtree rooted at the returned node does not contain key.
     */
    private static BSTNode remove(int key, BSTNode node) {
    	// if node is an empty tree...
    	if (node == null) {
    		//key was not in the tree, so return node as is     	
    		return null;
    	}

    	if (key < node.key) {
    		//remove key from the left subtree of node
    		node.left = remove(key, node.left);
    	}
    	else if (key > node.key) {
    		//remove key from the right subtree of node
    		node.right = remove(key, node.right);
    	}

    	//if key is located in node itself, here is where
    	// we do the actual work...
    	else {	 
    		//if node has no children, simply remove it 
    		// (ie, return null)
    		if (node.left==null && node.right==null) {
    			node = null;
    		}

    		//if node has one child, return a reference to that 
    		// child (it is the root of the only subtree of node)
    		else if (node.left==null && node.right!=null) {
    			node = node.right;
    		}
    		else if (node.left!=null && node.right==null) {
    			node = node.left;
    		}

    		//if node has two children...
    		else {
    			//find the node with the minimum key in the 
    			// right subtree of node
    			BSTNode minNode = findMin(node.right);
                
    			//replace node.key with minNode.key
    			node.key = minNode.key;

                //remove minNode from the right subtree of node
                // (we know that minNode has at most 1 child)
    			node.right = remove(minNode.key, node.right);
    		}
    	}//else (key==node.key)

    	//return a reference to (the updated subtree rooted at) node
    	return node;	    
    }//remove(int key, BSTNode node);

    /**
     * Find and return a reference to the node containing the 
     * minimum key in the subtree rooted at node. 
     * 
     * @param node
     *   The root of the subtree in which to search
     * @return 
     *   A reference to minNode, the node containing the minimum 
     *   key in the subtree rooted at node
     * @exception NullPointerException 
     *   If node==null
     * @pre
     *   The subtree rooted at node is not empty (i.e., node!=null).
     * @post
     *   The BST is unchanged.
     */
     private static BSTNode findMin(BSTNode node) {
    	//follow the left child until none exists
    	while (node.left != null) {
    		node = node.left;
    	}
    	//return the node that does not have a left child
    	return node;
    }//findMin(BSTNode node)

}//public class BST