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
Submit using assignment name written2. This assignment is worth 35 written assignment points.
You may assume the following standard definitions of ListNode
and TreeNode
exist in solving the problems below.
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;
}
}
You can use the following recurrence relations and solutions in the
problems below. That is, when the question asks you to give the bigOh, you do not need to derive the solution.
A  T(n) = T(n/2) + O(1)  O(log n) 
B  T(n) = T(n/2) + O(n)  O(n) 
C  T(n) = 2T(n/2) + O(1)  O(n) 
D  T(n) = 2T(n/2) + O(n)  O(n log n) 
E  T(n) = T(n1) + O(1)  O(n) 
F  T(n) = T(n1) + O(n)  O(n^{2}) 
G  T(n) = 2T(n1) + O(1)  O(2^{n}) 
 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
 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) {
}
 What is the complexity (using bigOh) of the solution you
wrote to hasDuplicates and why?
 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^{100} can be represented by TermNode(3,100,null);
and 7x^{50} + 2x^{5} + 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;
}
}
 Write a method makePolyNomial that takes a polynomial expressed in
array form in which
every term is explicitly stored (including those
with zerocoefficients) and returns a polynomial expressed in
linked list form (list of
TermNodes) in which
just terms with nonzero 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
3x^{4} + 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 zeroindex 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 zerocoefficent terms in list returned.
*/
public static TermNode makePolyNomial(int[] poly) {
 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^{4} + 2x + 4) + (2x^{2}  4x 9) =
(3x^{4} +2x^{2}  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) {
 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^{2} + 2x  2x  4, but your function should
actually return x^{2}  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
 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 bigOh 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;
}

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 bigOh complexity. Explain why the method works and justify
your recurrence.
/**
* Parameter tree is a search tree, listSoFar is the linked list
* constructed from alreadyvisited 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 kth 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 kth 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));
}
}

Assuming trees are roughly balanced (e.g., average case), write a
recurrence for
findKthInOrder
and give the
solution to the recurrence.
 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 bigOh 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) {
}
 Two trees s and t are quasiisomorphic 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 quasiisomorphism, only the
shape is important. The trees below are quasiisomorphic 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 quasiisomorphic. You must also give the bigOh 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 quasiisomorphic, 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 quasiisomporphic
*/
public static boolean isQuasiIsomorphic(TreeNode s, TreeNode t) {
}
Last modified: Wed Mar 30 16:54:56 EDT 2011