In general, since we are ignoring the "generics" features of Java, DrJava will occasionally complain with an "unchecked type warning" (or something similar).   Ignore these warnings -- they can be permanently suppressed by un-checking the appropriate box under "Preferences/Compiler Options" in DrJava.)

Now you're on a roll!  So let's move on to array equality.   There's a lot lost in going to arrays, namely polymorphism and intelligence.   Arrays cannot support visitors, so we have to write a separate utility class that takes in the arrays to be processed as input parameters.  Arrays have no internal sense of being empty or non-empty and not recursive data structures, so there things to be checked that in lists and trees are automatically taken care of by polymorphism. 

Write a class called ArrayUtils with a method called isEqual that takes in two arrays of Objects (i.e. type Object[]) and returns true if all the corresponding elements in the arrays are equal (as determined by their equals method).  false should be returned if any corresponding elements are not equal or the arrays are of different length.

• The ArrayindexOutOfBounds exception should never be thrown, no matter the length of either input array.
• Empty arrays should be valid inputs.   If both inputs are empty arrays, the return value should be true.
• If any corresponding elements are found to be not equal, then processing of the arrays should immediately terminate and the rest of the arrays ignored.   false should be returned.  

Problem 3 - Binary Search Tree (30 pts total)

The following is a proposed algorithm (by a student) to delete the root of a binary search tree of type BiTree.

• Empty Case: there is nothing to delete; do nothing.
• Non-empty Case:
  • When at least one of the subtree is empty: no problem, just remove the root.
  • When both subtrees are non-empty:
    • go to the left subtree and find the rightmost non-empty subtree, say rms;
    • set the right subtree of rms to be the right subtree of the original tree;
    • set the right subtree of the original tree to empty;
    • remove the root of the original tree (this can be done because its right subtree is now empty).

3.a. (10 pts)  Write a BiTree visitor called RemRootBST to remove the root of a binary search tree as described by the above algorithm.  The stub code in in the package brs.visitor of the provided project (prob3).

3.b. (5 pts) Compare the algorithm in 3.a against BSTDeleter, the algorithm to remove an element from a binary search tree given in lecture 36: http://www.owlnet.rice.edu/~comp201/06-spring/lectures/lec36/.  Discuss the pros and cons.  Write your answer as comments at the top of the visitor code.

3.c (15 pts)  Consider a binary search tree, specifically, the implementation presented in lecture using class BiTree. Write a BiTreevisitor named BSTFindNext that returns the BiTree object that is the next largest object relative to the visitor's input. The visitor's input may or may not be in the binary search tree. If there is no next larger element, return an empty BiTree.  The stub code in in the package brs.visitor.

Examples: Consider the following binary search tree containing Integer.

    57
   /  \
 33    78
      /  \
    63    91
   /  \
 59    71
      /
    70
                     

Let BiTree bst be the above binary search tree and bstfindnext be an instance of BSTFindNext.

• bst.execute(bstfindnext, 63) would return the BiTree containing 70 at the root.
• bst.execute(bstfindnext, 71) would return the BiTree containing 78 at the root.
• bst.execute(bstfindnext, 60) would return the BiTree containing 63 at the root.
• bst.execute(bstfindnext, 91) would return an empty BiTree.

Problem 4:  N-ary Trees (40 pts + 15 pts extra)

• An n-ary Tree can be empty or non-empty.
• An empty n-ary Tree contains nothing.
• A non-empty n-ary Tree contains a data element, an n-ary Tree called the left most child tree and an n-ary Tree called the right sibling tree.

The code for the above tree model is in the package tree of the supplied code (prob4).

Examples: Using horizontal lines to denote right sibling links and (slanted) vertical lines to denote left-most child links, and the letter ‘e’ to denote an empty n-ary tree, the following illustrates various n-ary trees and their corresponding leftmost child - right sibling representations.  For simplicity, the empty binary trees at the end of leaf nodes on the binary tree have been omitted.

	57

 
    57 -- e
    /
   e

 57    or     57      or     57
 |           /  \           /  \
 33         33   e         e   33

       57 -- e
     /
   33 -- e
  /   
 e    

    57
  /   \
 33   78

      57 -- e
     /
   33 -- 78 -- e
  /      /
 e      e

      57
   /   |   \
 33   78   12
    /    \
   63     19
  /  \   /  \
 42  e  e    6

      57 -- e
     /
   33 -- 78 -- 12 -- e
  /     /
 e    63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

4.a. (15 pts)   Write an ITreeVis algorithm called TreeEqual that will take another Tree as its input and return true if all the corresponding data elements in the host and input trees are equal (as determined by their equals method) and returns false otherwise.  The stub code for TreeEqual is in the package tree.visitor.  Hint: this algorithm is very similar to the algorithm in problem 1.  You may need to write anonymous helper visitors here.

4.b. (10 pts)   Write a JUnit test class called TestTreeEqual that tests the visitor TreeEqual in 3.a.  The test code must cover at least the following cases for the host:

• host is empty
• host is non-empty, in which case
  • leftmost child and right sibling are both empty
  • leftmost child is non-empty and right sibling is empty
  • leftmost child is empty and right sibling is non-empty
  • leftmost child and right sibling are both non-empty

You are to figure out what the various input Trees should be to thoroughly test the visitor.  The stub code for  TestTreeEqual  is in package tree.visitor.test.

4.c. (15 pts)  Like the case of the binary tree structure BiTree, we allow removal of the root only when the leftmost child is empty or when the right sibling is empty.  In the empty leftmost child case, when we remove the root node, the tree node is replaced by the node of its right sibling.  In other words, the tree mutates to become its original right sibling.  In the empty right sibling case, when we remove the root node, the tree node is replaced by its leftmost child.  In other words, the tree mutates to become its original leftmost child.  The root node cannot be removed when both leftmost child and right sibling are non-empty.  A IllegalStateException should be thrown in this case.  Below are some examples to illustrate the root removal specification.

     57 -- e
    /
  e

   33 -- 78 -- 12 -- e
  /     /
 e    63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

         78 -- 12 -- e
        /
      63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

      57 -- e
     /
   33 -- 78 -- 12 -- e
  /     /
 e    63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

   33 -- 78 -- 12 -- e
  /     /
 e    63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

         78 -- 12 -- e
        /
      63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

Complete the code for the method removeRoot() in NonEmpty.java to implement the above specification.

4.d. (15 pts extra)  Write a BiTree visitor called MakeTree that builds and returns an equivalent n-ary Tree for the BiTree host.  For examples,

    57
  /   \
 e     e

    57 -- e
    /
   e

    57
  /   \
 33   e

       57 -- e
     /
   33 -- e
  /   
 e    

    57
  /   \
 e     78

       57 -- e
     /
  78  -- e
  /   
 e    

    57
  /   \
 33   78

      57 -- e
     /
   33 -- 78 -- e
  /      /
 e      e

      57
   /     \   
 33       78   
        /    \
      63     19
     /  \   /  \
    42  e  e    6

      57 -- e
     /
   33 -- 78 --- e
  /     /
 e    63 ----- 19 -- e
     /         /
   42 -- e    6 -- e
  /          /
 e          e

           57
         /     \   
       33       78   
     /    \
    89     23
   /  \   /  \
 18  e  e    99

          57 -- e
         /
        33 ---------------- 78 --- e
       /                    /
      89 ----- 23 -- e     e
     /         /
   18 -- e    99 -- e
  /          /
 e          e

The stub code for MakeTree is in the package brs.visitor.  Feel free to write additional helper visitors if needed.

Hints (compare these hints with the above diagrams):

• Consider the fact that a binary tree represented as an n-ary tree never has any siblings at the root level.
• The left-most child of the n-ary tree representation could be either the left or right sub-tree of the binary tree, depending on whether or not the left sub-tree is empty.
• Think very carefully about when the binary-->n-ary conversion can be recursively applied.   For instance, consider what the right sub-tree of the binary tree always converts to in the n-ary tree representation. 
• Where do the n-ary representations of a entire non-empty left sub-tree and the entire right sub-tree of the binary tree end up with respect to each other in the overall n-ary representation of the binary tree?