Objectives

• Use recursion to implement a string reversal method
• Use recursion to implement a palindrome checking method
• Use recursion to implement inorder tree traversal

Note: All of these problems can be solved iteratively, but you will receive no points for doing so—this lab is on recursion!

Setup

First, create a lab11 directory:

$ cd cs190m
$ mkdir lab11
$ cd lab11

Then, download Lab11.java and Tree.java into the folder you just created.

Task 1: String Reversal

Write a recursive algorithm to reverse a String. You should write your code in the reverse method stub. You are, however, welcome to write helper methods if necessary (the same applies for the other two problems).

Task 2: Palindrome Checking

A palindrome is sequence of characters that, when reverse, is still the same sequence. For example, "radar" and "12321" are palindromes, but most words in this lab description are not. Write a recursive algorithm to determine whether or not a String is a palindrome. Place your implementation inside of the isPalindrome method stub.

Task 3: Inorder Tree Traversal

This last task deals with traversing the elements of a binary tree. Inside of the main method, you'll see that a Tree object has been created for you. The class is a very simple representation where each tree holds an integer element, as well as left and right sub-trees. There is no code for inserting or removing elements, but you can see that the tree conforms to the definition of a binary search tree, where all elements in the left sub-tree of a node are smaller than the element at that node and all elements in the right sub-tree of a node are greater. As such, an inorder traversal that prints all of the elements of the tree should print in numerical order.

Inorder traversal can be easily defined recursively. To traverse a tree in order, you should:

1. Traverse the left sub-tree in order
2. Visit the element at the top of the tree
3. Traverse the right sub-tree in order

Your task is to implement inorderPrint recursively, which is a Tree method that will traverse the tree in order and print the integer elements along the way. You can visualize what the tree should look like, since the indentation represents different heights of the tree. Thus, 15 is at the top of the tree, with left and right children being 10 and 20. The sub-tree that has element 10 has left and right children 5 and 13, etc. If your code is correct, it should print the elements in order (ie, "5 10 13 15 17 20 25").

Testing Your Lab

Some basic tests are provided for you in the main method of the Lab11 class. You may consider adding your own testcases either in the main method or in a JUnit test class.

Turning In Your Lab

To turn in your lab:

$ cd ~/cs190m/lab11
$ turnin -v -c cs190m -p lab11 *.java

Getting Help

Many of you will probably run across problems while programming at some point during a lab. If that's the case, here are the resources you should use, in order:

1. Your textbook
2. Lecture notes
3. Java API documentation
4. Your lab TA

Lab created by: Daniel Tang