CS 206 - Introduction to Data Structures

Lab 11/07


Recursion is a very useful programming technique. But it tends to be slow and memory intensive. Hence, when possible, many programmers try to avoid it. A common technique is to first write a program using recursion, then re-write it to eliminate recursion. In this lab you will be doing just that.
  1. Download IBinaryTreeArray.java from /home/gtowell/Public206/Lab1114. This is a fairly standard implementation of an array binary tree except that it is tied to Integers and includes only an insert method and a inorder printer.
  2. Create a driver method for this class. In your driver add: 6, 4, 2, 7, 3, 9, 8, 5 in that order. This will create a tree with the following structure: 
                            6
                 /-----/ \-----\
                /               \
               4                 7
            /-/ \-\           /-/ \-\
          /         \        /       \
         2           5      x         9
        / \                          / \
       x   3                        8   x
  3. Re-implement insert without recursion
  4. Consider reimplementing the method for printing nodes in numeric order without recursion. Spend several minutes with a pen and paper drawing the exact steps that this method will need to perform. You should discover that printing in-order without recursion is a pain. The problem is handling backtracking.
  5. An auxiliary data structure will help in your non-recursive printer. The obvious data structure to use is a stack. After all, recursion is implemented using stacks. Java provides one (java.util.Stack). Look up the definition of the java stack class. Use the java stack class to implement a non-recursive pre-order printer for your tree. Note that a pre-order printer of the tree will not print the in numeric order. Rather it will print the tree above as: 
    	
6 4 2 x 3 5 7 x 9 8 x
    (the x's are optional) (Pre-order is much easier to implement non recursively than in-order. Why?).
  6. Consider the recursive H printer discussed in class on Nov 12. Get a copy from /home/gtowell/Public206/Lab1114/FH.java. Implement this non-recursively without using a stack. More specifically, do not use a the java Stack class. Neither should you use the java Queue class, nor should you use ArrayList (or array) in a way that simulates the behavior of a stack or a queue.
  7. Get a copy of the merge sort code for linked lists from /home/gtowell/Public206/Lab1114/MergeSortLL.java Run it with increasing sizes of things to sort. The code dies somewhere between 20,000 and 40,000 items on my machine with a stack overflow error. Where does it die for you? The stack overflow error occurs during the list sortedmerge function which is implemented recursively. Rewrite sortedmerge to be non-recursive. How big a list can you sort with your re-implementation?
  8. Think about how to adjust your pre-order printer to make it in-order with no additional auxiliary structures. Doing so is tricky. (The way I did it used a real "kludge".) Maybe you can come up with something clean. Try.
  9. Using a stack is kind of a cop out. After all, recursion is just a form of stacks. Can you think of another auxiliary data structure that would allow you to accomplish this task. (Tur jnl I pnzr hc jvgu vf irel fcnpr varssvpvrag. Ig hfrf na neenl bs vagf gung vf gur fnzr fvmr nf gur onpxvat neenl.) This is encrypted using a rot13 cypher.