Homework: BinaryTree and Recursion I

This homework is necessary preparation for the lab.

1. Write a recursive body for the following static, generic method that computes and returns the size of a given BinaryTree<T>. You can use any of the BinaryTree methods except for the iterator and the size kernel method. Note that the BinaryTree must be restored, i.e., its outgoing value must be the same as its incoming value.

   /**
    * Returns the size of the given {@code BinaryTree<T>}.
    * 
    * @param <T>
    *            the type of the {@code BinaryTree} node labels
    * @param t
    *            the {@code BinaryTree} whose size to return
    * @return the size of the given {@code BinaryTree}
    * @ensures size = |t|
    */
   public static <T> int size(BinaryTree<T> t) {...}
   

2. Provide a second implementation of the size method above but this time make it an iterative (non-recursive) solution. You cannot use the size kernel method in your solution.

Additional Questions

1. Write a recursive body for the following static, generic method that computes and returns the height of a given BinaryTree<T>. You can use any of the BinaryTree methods except for the height method. Note that the BinaryTree must be restored, i.e., its outgoing value must be the same as its incoming value.

   /**
    * Returns the height of the given {@code BinaryTree<T>}.
    * 
    * @param <T>
    *            the type of the {@code BinaryTree} node labels
    * @param t
    *            the {@code BinaryTree} whose height to return
    * @return the height of the given {@code BinaryTree}
    * @ensures height = ht(t)
    */
   public static <T> int height(BinaryTree<T> t) {...}