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.

You may not use the Internet to do these problems, no Googling.

It is important to think about your answers, not to run them.

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.

Assume the following declarations have been made, note that a TreeNode has a parent pointer, assume this is properly initialized/set to point to the node's parent in tree. public 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.
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. 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.
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)); } }
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 == 0) return null; 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)); }
1. 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.
2. 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.
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.
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.