Homework: Tree and Recursion

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

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

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

3. Write a recursive body for the following static, generic method that computes and returns the height of a given Tree<T>. You can use any of the Tree methods except for the height kernel method (in particular, you can use the size method). Note that the Tree must be restored, i.e., its outgoing value must be the same as its incoming value.

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

4. Write a recursive body for the following static method that computes and returns the largest integer in a given non-empty Tree<Integer>. Note that the Tree must be restored, i.e., its outgoing value must be the same as its incoming value.

   /**
    * Returns the largest integer in the given {@code Tree<Integer>}.
    * 
    * @param t
    *            the {@code Tree<Integer>} whose largest integer to return
    * @return the largest integer in the given {@code Tree<Integer>}
    * @requires |t| > 0
    * @ensures <pre>
    * max is in labels(t)  and
    * for all i: integer where (i is in labels(t)) (i <= max)
    * </pre>
    */
   public static int max(Tree<Integer> t) {...}
   

Additional Questions

1. Write a recursive body for the following static, generic method that returns a String representation of a given Tree<T>. You cannot use the Tree toString method in your solution. Note that the Tree must be restored, i.e., its outgoing value must be the same as its incoming value.

   /**
    * Returns the {@code String} prefix representation of the given
    * {@code Tree<T>}.
    * 
    * @param <T>
    *            the type of the {@code Tree} node labels
    * @param t
    *            the {@code Tree} to convert to a {@code String}
    * @return the prefix representation of {@code t}
    * @ensures treeToString = [the String prefix representation of t]
    */
   public static <T> String treeToString(Tree<T> t) {...}
   

   The prefix representation of the empty tree is "()", and the prefix representation of a non-empty Tree<T> is the string concatenation of the root, followed by '(', then by the prefix representation of subtrees in the order in which they appear in the tree, and finally ')'. Here are five examples of prefix representations of some Tree<Character>s. See if you can figure out and draw the trees being described.

   • ()
   • a(()()())
   • a(b()c(d(e()))f(()))
   • a(()b()()c())
   • a(()b(c(()())()d()))

2. Write a recursive body for the following static method that copies and returns a given Tree<Integer>. Note that the given Tree must be restored, i.e., its outgoing value must be the same as its incoming value.

   /**
    * Returns a copy of the given {@code Tree<Integer>}.
    * 
    * @param t
    *            the {@code Tree<Integer>} to copy
    * @return a copy of the given {@code Tree<Integer>}
    * @ensures copy = t
    */
   public static Tree<Integer> copy(Tree<Integer> t) {...}