Design the method getFirst that produces the first Book in the binary search tree (as given by the appropriate ICompareBooks.

In the Leaf class this method should have the following body:

throw new RuntimeException("No first in an empty tree");

Design the method getRest that produces a new binary search tree with the first Book removed.

In the Leaf class this method should have the following body:

throw new RuntimeException("No rest of an empty tree");

Design the method sameTree that determines whether this binary search tree is the same as the given one (i.e., has matching structure and matching data in all nodes).

Design the method sameData that determines whether this binary search tree contains the same books as the given tree.

Note: Given the following three trees:

bstA:       bstB:       bstC:       bstD:       
     b3          b3          b2          b3
    /  \        /  \        /  \        /  \
   b2  b4      b2  b4      b1   b4     b1   b4
  /           /                /             \ 
b1           b1               b3              b5

• bstA is the same tree as bstB

• bstA is not the same tree as bstC

• bstA is not the same tree as bstD

• bstA has the same data as bstB

• bstA has the same data as bstC

• bstA does not have the same data as bstD

We would like to know whether a binary search tree of books contains the same data as a list of books. Design the method that allows us to make this comparison.

Write a short explanation of your design.

Note: You are allowed to introduce new classes or interfaces to solve this problem.

Design a new bstSort method for the classes that represent a list of books, that first builds a binary search tree from the data in this list, then converts the binary search tree into a sorted list.

Write a short explanation of your design.

6.3  Problem

In this problem you will start with your solution to Problem 5.4 in the previous assignment, and use some of the code you have written for the Problem 3.1.

1. Start with a new project that includes your solution to the Problem 5.4.

2. Design a class Capitol that represents a capitol of one of the 48 US states (not Alaska or Hawaii). This class should extend the class Place. This class should have the following features:

   • The field name should be the state abbreviation.

   • There should be a constructor that consumes the same data in the same order as you have done for the class City in Problem 3.1, with the list of neighbors as an additional last argument.

   • The conversion from the latitude and longitude data to CartPt should emulate the method toPosn in the Problem 3.1. If you wish, you can change the size of the Canvas to be 300 x 300.

3. Make sure all methods you have designed for the class StateMap including the animation of the routing works correctly.