Compsci 100, Fall 2006, Written Tree Questions
These problems provide practice with trees, recursion, and big-Oh.
You can talk about the problems with up other people, but each person
should submit his/her own version of the solutions. This means
your writeups should be your own work, even if you talk with
other people. It's in your own interest to do your own work
as test questions will be difficult if you cannot do these questions.
This assignment is worth 35 points. You should work on your own, 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.
Please write your solutions by hand, using pencil/pen etc. Do NOT use
Eclipse or a computer. We want you to practice thinking, writing
by hand. Hopefully you'll rewrite to make things neat. If we can't
read your writing, we'll think it's wrong.
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.
You'll submit a README electronically using Eclipse, but you'll turn in
your written work: stapled, your name on every page. Your README file
should indcate how long you spent on these problems and with whom you
consulted. Please do NOT turn in the assignment on the pages given
to you, write on other paper.
Submit the README using Eclipse (assignment name trees)
Again, do not run and debug. Instead, think. This is
good practice for thinking, for test-taking, and for programming which
should include time not spent at the machine.
Assume the following declaration has been made and that
the TreeNode class is an inner class of the
class TreeProblems in which you'll write methods
to solve the problems below.
public static class TreeNode
{
String info;
TreeNode left;
TreeNode right;
TreeNode parent;
TreeNode (String s, TreeNode lt, TreeNode rt, TreeNode p)
{
info = s;
left = lt;
right = rt;
parent = p;
}
}
- Write a static method that returns a copy of a tree. For every node in
the tree passed as a parameter a new node should be constructed and
linked into the tree being returned, the nodes should be in the same
location relative to the right as in the original tree, i.e., the trees
should be exact copies. A copy function for lists is provided as an
example.
public static ListNode copy(ListNode list) {
if (list == null) return null;
return new ListNode(list.info, copy(list.next));
}
public static TreeNode copy(TreeNode root) {
}
-
- 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(tree.info, afterMe);
if (beforeMe == null) 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 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);
}
-
Write the method levelCount whose header is given below.
levelCount returns the number of nodes on the specified
level.
For this problem, the root is at level zero, the root's children are
at level one, and for any node, the node's level is one more than its
parent's level. For example, for the bean-tree diagrammed below, the
call levelCount(t,1) should return 2 (chickpea and navy are
on level 1); the call levelCount(t,2) should return 3; and
the call levelCount(t,4) should return 0.
Hint: when the level is 0, there is always just one node at that level,
the root node (assuming t isn't empty), so return 1. If the level isn't
zero, recursive calls will be used to determine the number of nodes at
the requested level, and the level-requested should change in the
recursive calls.
/**
* Returns number of nodes at specified level in t,
* where level >= 0.
* @param level specifies the level, >= 0
* @param t is the tree whose level-count is determined
* @return number of nodes at given level in t
*/
public static int levelCount(TreeNode t, int level){
}
-
(Assume nodes store integers for this problem).
Write the method hasPathSum whose header is given below.
hasPathSum returns true if there exists some root-to-leaf
path in the tree whose root is t whose nodes sum to
target and returns false otherwise.
For example, in the tree shown below there are exactly four
root-to-leaf paths. The sums of the paths are 27, 22, 26, and 18.
Thus the value of hasPathSum(t,27) should be true and the
value of hasPathSum(t,30) should be false (assuming
t points to the root of the tree --- the node whose info
field has value 5.)
Hint: You should make two recursive calls, you must decide on the value
of target for each recursive call so that you can use the return
values of the recursive calls to solve the problem. Note: in a tree
with one node (a leaf) you can determine immediately if there's a path
that sums to the target based on whether the target and the node are equal.
/**
* Return true if and only if t has a root-to-leaf path
* that sums to target.
* @param t is a binary tree
* @param target is the value whose sum is searched for on some
* root-to-leaf path
* @return true if and only if t has a root-to-leaf path summing to target
*/
public static boolean hasPathSum(TreeNode t, int target) {
}
KthInOrder Questions
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 == null) 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));
}
}
-
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?
- By definition, the
diameter of a tree (sometimes called the width) is the number
of nodes on the longest path between two leaves in the tree. The
diagram below shows two trees each with diameter nine, the leaves that
form the ends of a longest path are shaded (note that there is more
than one path in each tree of length nine, but no path longer than
nine nodes).
It can be shown that the diameter of a tree T is the largest
of the following quantities:
- the diameter of T's left subtree
- the diameter of T's right subtree
- the longest path between leaves that goes through the root of T
(this can be computed from the heights of the subtrees of T)
Here's code that's almost a direct translation of the three properties
above.
public static int diameter(TreeNode t)
{
if (t == null) return 0;
int leftD = diameter(t.left);
int rightD = diameter(t.right);
int rootD = height(t.left) + height(t.right) + 1;
return Math.max(rootD, Math.max(leftD, rightD));
}
-
However, the method as written does not run in O(n) time.
Write a recurrence for this implementation and what the solution
to the recurrence is. Assume trees are roughly balanced in writing
the recurrence.
- Write a version of diameter that runs in O(n) time.
Your method should use an auxiliary/helper method as described
below. The helper method should make
two recursive calls and do O(1) other work.
/**
* Return height and diameter of t, return height as
* value with index 0 and diameter as value with index 1
* in the returned array.
* @param t is a binary tree
* @return array containing both height (index 0) and diameter (index 1)
*/
public static int[] diameterHelper (TreeNode t) {
// write this
}
public static int diameter(TreeNode t)
// post: returns diameter of t
{
int[] ret = diameterHelper(t);
return ret[1];
}
-
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) {
}
-
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) {
}