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

Extra Credit
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.

Extra Credit

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.