Compsci 100, Fall 2009, October 23 Recitation


Name: _____________________  Netid: _________________


Name: _____________________  Netid: _________________
 

Name: _____________________  Netid: _________________

recitation code submitted, use oct23-rec to submit code for student review.

Tree Questions

These questions use the TreeNode definition below. public class TreeNode { String info; TreeNode left; TreeNode right; TreeNode (String s, TreeNode lt, TreeNode rt) { info = s; left = lt; right = rt; } }
  1. Write the method levelCount whose header is given below. Method 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 N its level is one more than N's 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){ }

  2. Write the method hasPathSum whose header is given below. Method 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. So identification of a leaf-node will likely be a base case in your recursive method.

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

  3. 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:

    *

    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]; }
  4. 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) { }
  5. 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) { }