CompSci 100E, Spring 2011
Written List & Tree Exercises

You should work independently on this assignment, but you can use books/notes. You should not use the web as a resource for solving problems. Please do NOT compile and do not run your solutions. Where we asked to write code, do NOT use Eclipse. We want you to practice thinking and writing solutions in the form that you would write on an exam. You can write your solutions by hand and scan them or type everything using your favorite text editor in a text file.

Do NOT worry about perfect syntactic correctness, your grade is based on the algorithms you use/invent, not on whether the code compiles. However, you must write something close to correct in Java.

As with all assignments, you will submit:

• README.txt that indicate how long you spent on these problems, what resources you used, and with whom you consulted
• written2.txt or written2.pdf with your solutions

public class ListNode {
    String info;
    ListNode next;
    ListNode(String s, ListNode link) {
        info = s;
        next = link;
    }
}

public class TreeNode {
    String info;
    TreeNode left;
    TreeNode right;
    TreeNode(String s, TreeNode l, TreeNode r) {
        info = s;
        left = l;
        right = r;
    }
}

Fruit Salad

Write the method fruitCounter whose header follows. Method fruitCounter returns a count of the number of nodes whose info field has a value for which a static method isFruit (see below) returns true. public static boolean isFruit(String s){ // code not shown } For example, assuming that "apple", "orange", and "pear" are fruits (isFruit returns true) and "bear", "coyote", and "fox" are not fruits, and list is represented by:

   ("apple", "bear", "apple", "orange", "coyote", "fox", "orange", "pear")

the call fruitCounter(list) should evaluate to 5 since there are five fruits.

Write two versions, one iterative and one recursive.

/** * @return the number of nodes whose info field is a fruit * as determined by method isFruit */ public static int fruitCounter(ListNode list) {

Occurs Check

1. Write a method hasDuplicates whose header follows. The method returns true if parameter list has any duplicates (words occurring more than once) and false otherwise. For example, for the list

    ( "apple", "guava", "cherry")
   

   hasDuplicates should return false, but it would return true for the list below since "guava" appears twice.

    ( "apple", "guava", "cherry", "guava")
   

   In writing hasDuplicates you must call the method countOccurrences shown below and your method must be either a recursive function with no loop or a function with one loop. Either version can include calls to countOccurrences. You cannot use any ArrayList, Set, etc. objects in your code. /** * @return the number of occurrences of s in list */ public static int countOccurrences(ListNode list, String s) { if (list == null) return 0; int count = 0; if (list.info.equals(s)) count = 1; return count + countOcurrences(list.next,s); } /** * @return true if and only if list has duplicates * */ public static boolean hasDuplicates(ListNode list) { }

2. What is the complexity (using big-Oh) of the solution you wrote to hasDuplicates and why?

3. Describe how to write a more efficient solution to the hasDuplicates method using, for example, a TreeSet or a HashSet instead of calling countOccurrences. Be sure to indicate what the complexity of your solution is and why.

Polynomial. Polygon.

The following problems use the class TermNode below to represent a single term of a polynomial. For example 3x¹⁰⁰ can be represented by TermNode(3,100,null); and 7x⁵⁰ + 2x⁵ + 8 is represented by

  TermNode poly = new TermNode(7,50, new TermNode(2,5, new TermNode(8,0,null)));

Here's the class definition. public class TermNode { int coeff; int power; TermNode next; TermNode(int co, int po, TermNode follow) { coeff = co; power = po; next = follow; } }
1. Write a method makePolyNomial that takes a polynomial expressed in array form in which every term is explicitly stored (including those with zero-coefficients) and returns a polynomial expressed in linked list form (list of TermNodes) in which just terms with non-zero coefficients are stored. For example, given a array of [3, 0, 0, 2, 5], your function should return the list ( (3, 4), (2, 1), (5,0) ) since both represent

   3x4 + 2x + 5

   Here we assume the 5 in the array has index 0 and the 3 has index 4, so the array is shown with the zero-index on the right (but your method doesn't have a right or a left, just an array with a length and int coefficients).

   /** * Returns a list of TermNodes representingy poly, * the elements in poly are in sorted order by power/exponent * with largest exponent first, no zero-coefficent terms in list returned. */ public static TermNode makePolyNomial(int[] poly) {
2. Write a method addPolyNomial that takes two polynomials expressed as lists of TermNodes, and returns a new polynomial representing the sum of the two parameters. The parameters should not be altered as a result of calling addPolynomial, a new polynomial is created and returned.

   For example, (3x⁴ + 2x + 4) + (2x² - 4x -9) = (3x⁴ +2x² - 2x - 5)

   ((3,4),(2,1),(4,0)) + ((2,2),(-4,1),(-9,0)) = ( (3,4),(2,2),(-2,1),(-5,0) )
   // pre: elements in p1 and p2 are sorted by power, largest to smallest // (standard form for this problem) // post: returns polynomial/list of TermNodes // representing the sum of p1 and p2 /** * Return polynomial in standard form of two standard form polynomials. * @param p1 is sorted by power, large to small, standard form * @param p2 is sorted by power, large to small, standard form * @return polynomial representing sum of p1 and p2 */ public static TermNode addPolyNomial(TermNode p1, TermNode p2) {
3. Extra credit: Write a method multPolyNomial that returns the simplified result of multiplying this TermNode with another polynomial.

   For example (x - 2) * (x + 2) = x² + 2x - 2x - 4, but your function should actually return x² - 4 or

   multPolyNomial( ((1,1),(2,0)), ((1,1),(-2, 0)) ) => ( (1,2),(-4, 0) ) /** * Return polynomial in standard form of product of two standard form polynomials. * @param p2 is sorted by power, large to small, standard form * @return polynomial consisting of new TermNodes representing * product of this and p2. The polynomial should have no redundant terms */ public static TermNode multPolyNomial(TermNode p2) {

TreeToList Revisited

1. The method treeToList below converts a search tree into a sorted linked list. For example, if root points to to the root (melon) of this tree:

                   melon
                  /     \
               grape    pear
               /   \        \
              /     \        \
            apple   lemon   tangerine
   

   the call

      ListNode list = treeToList(root);
   
   

   will return a list represented by the following

     ("apple", "grape", "lemon", "melon", "pear", "tangerine")
   

   This function is correct. Write a recurrence relation for this function assuming that the tree passed in (and all subtrees) are roughly balanced (so each subtree contains roughly half as many nodes as the entire tree) and give the big-Oh complexity of the function. Justify your recurrence with words.
   public static ListNode treeToList(TreeNode tree) { if (tree == null) return null; ListNode beforeMe = treeToList(tree.left); ListNode afterMe = treeToList(tree.right); ListNode me = new ListNode(list.info, afterMe); if (beforeMe == nll) return me; // nothing before me, so done ListNode current = beforeMe; // find last node of beforeMe list while (current.next != null) { current = current.next; } current.next = me; // link last node to me and afterMe return beforeMe; }
2. Here's another version of treeToList that works by calling a recursive helper method. public static ListNode treeToList(TreeNode tree) { return treeToListHelp(tree, null); } Write a recurrence relation for the helper method below assuming that the tree passed in (and all subtrees) are roughly balanced (so each subtree contains roughly half as many nodes as the entire tree) and give its big-Oh complexity. Explain why the method works and justify your recurrence. /** * Parameter tree is a search tree, listSoFar is the linked list * constructed from already-visited part of search tree * This method returns a sorted list with all nodes from tree */ public static ListNode treeToListHelp(TreeNode tree, ListNode listSoFar){ if (tree == null) return listSoFar; ListNode afterMe = treeToListHelp(tree.right, listSoFar); ListNode me = new ListNode(tree.info, afterMe); return treeToListHelp(tree.left, me); }

Find K^th

You're to analyze the code in the method findKthInOrder whose header is given below. Given an integer k and a binary search tree with unique values, findKthInOrder returns a reference/pointer to the node that contains the kth element if the elements are in sorted order --- the smallest value is k == 1, the second smallest is k == 2, and so on.

For example, in the tree t shown below (t points to the root), findKthInOrder(t,4) returns a reference/pointer to the node with value 9, findKthInOrder(t,8) returns a reference/pointer to the node with value 18, and findKthInOrder(t,12) returns null since there are only 9 nodes in the tree.



The method count discussed in lecture returns the number of nodes in a tree.

/** * Returns number of nodes in t. * @param t is the tree whose nodes are counted * @return number of nodes in t */ public static int count(TreeNode t) { if (t == 0) return 0; return 1 + count(t.left) + count(t.right); } /** * Returns reference to k-th node when values considered * in sorted order, return null if t has fewer than k nodes * @param t is a binary search tree * @param k specifies which value in t to return * @return k-th value when nodes considered in order */ public static TreeNode findKthInOrder(TreeNode t, int k) { if (t == null) return null; // can't find anything, empty int numLeft = count(t.left); if (numLeft + 1 == k) { // current node return t; } else if (numLeft >= k) { // in left subtree return findKthInOrder(t.left, k); } else { return findKthInOrder(t.right, k - (numLeft + 1)); } }
1. Assuming trees are roughly balanced (e.g., average case), write a recurrence for findKthInOrder and give the solution to the recurrence.

2. Write a recurrence for findKthInOrder for the worst case, i.e., when a tree is completely unbalanced and the method is called to do the most work on every recursive call. What is the solution to this recurrence?

Isomorphic Trees

Two binary trees s and t are isomorphic if they have the same shape; the values stored in the nodes do not affect whether two trees are isomorphic. In the diagram below, the tree in the middle is not isomorphic to the other trees, but the tree on the right is isomorphic to the tree on the left.



Write a method isIsomorphic that returns true if its two tree parameters are isomorphic and false otherwise. You must also give the big-Oh running time (in the average case, assuming each tree is roughly balanced) of your method with a justification. Express the running time in terms of the number of nodes in trees s and t combined, i.e., assume there are n nodes together in s and t with half the nodes in each tree.

/** * Retrns true if s and t are isomorphic, i.e., have same shape. * @param s is a binary tree (not necessarily a search tree) * @param t is a binary tree * @return true if and only if s and t are isomporphic */ public static boolean isIsomorphic(TreeNode s, TreeNode t) { }
1. Two trees s and t are quasi-isomorphic if s can be transformed into t by swapping left and right children of some of the nodes of s. The values in the nodes are not important in determining quasi-isomorphism, only the shape is important. The trees below are quasi-isomorphic because if the children of the nodes A, B, and G in the tree on the left are swapped, the tree on the right is obtained.

   

   Write a method isQuasiIsomorphic that returns true if two trees are quasi-isomorphic. You must also give the big-Oh running time (in the average case, assuming each tree is roughly balanced) of your method with a justification. Express the running time in terms of the number of nodes in trees s and t combined as with the previous problem.

   /** * Returns true if s and t are quasi-isomorphic, i.e., have same shape. * @param s is a binary tree (not necessarily a search tree) * @param t is a binary tree * @return true if and only if s and t are quasi-isomporphic */ public static boolean isQuasiIsomorphic(TreeNode s, TreeNode t) { }