Week 13, 11/20

Prelab Exercises

1. Complete the List & Tree exercises.
2. Review Recurrence notes

Lab Exercises

The tree below is a binary search tree.



1. There are three tree-traversal routines below. In class we discussed the in-order traversal which prints a search tree in order. Given the code below, what's the pre-order and post-order traversals of the tree above, i.e., what's printed by calling each routine with a pointer to the root (macaque) of the tree above?

   public void preorder(Tree root) { if (root != null) { System.out.println(root.info); preorder(root.left); preorder(root.right); } }

   public void inorder(Tree root) { if (root != null) { ineorder(root.left); System.out.println(root.info); inorder(root.right); } }

   public void postorder(Tree root) { if (root != null) { postorder(root.left); postorder(root.right); System.out.println(root.info); } }

2. Provide a word (it doesn't have to be a real word, it must contain at least four letters) that could be inserted as a left-child of monkey so that the tree is still a search tree.

3. Show by drawing where a node with gibbon would be inserted into the tree.

4. The tree above has a height of four and has three leaves. Draw a search tree with the same values, a height of four, and which has four leaves.

5. 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 and the method height. The height of a tree is the length of the longest root-to-node path in the tree. For example, in the diagrams above the height of the both trees is six.

   public static int height(TreeNode t){ if (t == null) return 0; return 1 + Math.max(height(t.left), height(t.right)); } 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. What is the recurrence relation for height? In writing the recurrence let T(n) be the complexity of calling height with an n-node tree. Assume trees are roughly balanced so that there are about n/2 nodes in each subtree. What is the recurrence if the tree is completely unbalanced, e.g., all nodes in the left sub-tree?

   2. The method diameter as written above 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.

   3. We can write a version of diameter that runs in O(n) time. The recursion must return both the diameter and height of the left and right subtree in one call. To get two values we'll use an array in which the height is stored at index 0 and the diameter at index 1. A helper method is used as shown below. This method is O(n) because there is O(1) work done in addition to the two recursive calls.

      Fill in the missing code in diameterHelper so that it works as intended.

      /** * Return both 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) { int[] ret = new int[2]; // return this array if (t == null) { ret[0] = 0; // height is 0 ret[1] = 0; // and diameter is 0 return ret; } int[] left = diameterHelper(t.left); int[] right = diameterHelper(t.right); ret[0] = 1 + Math.max(left[0],right[0]); // this is height // fill in value for ret[1] below } public static int diameter(TreeNode t) { int[] ret = diameterHelper(t); return ret[1]; }
6. 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. Write a recurrence to justify the runtime complexity.

   Hint: a null trees is not isomorphic to a non-null tree, but two null trees are isomorphic. That's most-to-all of the base case you'll need. If the two trees have isomorphic left subtrees and isomorphic right subtrees, then they must be isomorphic.

   /** * 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) { }
7. 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. Write a recurrence and solve it! You'll need to do this because the recurrence is not one of the five-to-six recurrences we've seen before.

   The difference in quasi-isomorphism compared to isomorphism is that if the left subtree of one tree is quasi-isomorphic to the right subtree of the other, the trees might be quasi-isomorphic. Of course if the left subtrees are quasi-isomorphic the trees could be quasi-isomorphic as well.

   /** * 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) { }