/**
 * Description of the class.
 *   @author dwr46301
 *   @version October 11, 2006
 *
 */
public class BST {
    public static <E extends Comparable<? super E>> 
                  TreeNode<E> findNode(TreeNode<E> current, E value) {
        if (current == null || value.compareTo(current.getData()) == 0) {
            return current;
        }
        else if (value.compareTo(current.getData()) < 0) {
            return BST.findNode(current.getLeft(), value);
        }
        else {
            return BST.findNode(current.getRight(), value);
        } 
    }
    
    public static <E extends Comparable<? super E>> 
                  TreeNode<E> add(TreeNode<E> current, E value) {
        if (current == null) {
            return new TreeNode<E>(value, null, null);
        }
        
        if (value.compareTo(current.getData()) <= 0) {
            current.setLeft(BST.add(current.getLeft(), value));
        }
        else {
            current.setRight(BST.add(current.getRight(), value));     
        }
        return current;   
    }
    
    public static <E extends Comparable<? super E>> 
                  TreeNode<E> remove(TreeNode<E> current, E value) {
        if (current == null) {
            return null;
        }
        
        if (value.equals(current.getData())) {
            if (current.getLeft() == null) {
                current = current.getRight();
            }
            else {
                current.setData(BST.lastNode(current.getLeft()).getData());
                current.setLeft(BST.remove(current.getLeft(), current.getData()));
            }
        }
        else if (value.compareTo(current.getData()) < 0) {
            current.setLeft(BST.remove(current.getLeft(), value));
        }
        else {
            current.setRight(BST.remove(current.getRight(), value));
        }
        return current;
    }
    
    public static <E extends Comparable<? super E>> 
                  TreeNode<E> firstNode(TreeNode<E> current) {
        if (current == null) {
            return null;
        }
        
        while (current.getLeft() != null) {
            current = current.getLeft();
        }
        return current;
    }
    
    public static <E extends Comparable<? super E>> 
                  TreeNode<E> lastNode(TreeNode<E> current) {
        if (current == null) {
            return null;
        }
        
        while (current.getRight() != null) {
            current = current.getRight();
        }
        return current;
    }  
    
    public static <E extends Comparable<? super E>> 
                  String toString(TreeNode<E> current) {
        if (current == null) {
            return "[]";
        }
        
        String recStr = BST.stringify(current);
        return "[" + recStr.substring(0,recStr.length()-1) + "]";
    }
    
    private static <E extends Comparable<? super E>> 
                   String stringify(TreeNode<E> current) {
        if (current ==  null) {
            return "";
        }

        return BST.stringify(current.getLeft()) +
               current.getData().toString() + "," +
               BST.stringify(current.getRight());
    }
    
    public static <E extends Comparable<? super E>>
                  int height(TreeNode<E> current) {
        if (current == null) {
            return 0;
        }
        else {
            return Math.max(BST.height(current.getLeft()),
                            BST.height(current.getRight())) + 1;
        }
    }
}