CpSc 210, Section 1
                             Assignment 9 
                            November 13, 2002      



Due:  Friday, November 22, at 11:59 p.m.  

Assignment:  Extend Bailey's BinaryTree class to include a method which
      checks whether or not a BinaryTree is a BinarySearchTree.
	

Total point value of assignment:  50 points
Not accepted late.

This assignment is to be done INDIVIDUALLY.

Assignment:  Design and implement a class, CheckBST as an extension of
     Bailey's BinaryTree, which must be stored in a file named
     CheckBST.java.  (10 point deduction for failure to name file 
     correctly!)  

Bailey's BinaryTree code may be found at the "View the Local Source"
link from

     http://www.mhhe.com/javastructures


The BinaryTree interface is given on pages 190-191 of Java Structures.
You may include any private methods you want.

You will want to import structure.BinaryTree.

The signature of the required method is

    	public boolean isBST();
        // pre:  this tree is not empty
        // post:  returns true if this tree is a binary search tree
        //        otherwise, returns false.


Grading Rubric:

     5 pts. reasonable attempt to solve problem as assigned
     5 pts. also compiles
     5 pts. style standards (includes clarity)

            Now that we are dealing with references, the comment after
            exit from "while" loops is especially important.  The comment
            on an "else" is also useful.  One point will be deducted
            for each missing comment (maximum of 5) in the code
            that you write.  (Yes, we know Bailey does not have these
            and you cannot correct his code, but you can write yours
            in this manner.)
  
            Don't forget any needed pre- and post-conditions.
 
    The following 35 points are available only for code that compiles 
    without error.   Some considerations are:

    20 pts. code of isBST method returns correct answer
     5 pts. evidence that  your test driver (main method) systematically
	        checks for errors.

    The BinaryTree shown below is not a binary search tree.  Your code
    should include this tree in test cases.

                                    25
                                  /    \   
                               15        35
                             /    \    /    \
                           8     27   11      100
                             \          \   /
                              23        56  14

    The following 10 points are available only for code that 
    returns correct answer:

     5 pts. growth rate of equals method is best possible 
     5 pts. elegance of code