Compsci 100, Fall 2009, October 16 Recitation

Name: _____________________  Netid: _________________


Name: _____________________  Netid: _________________
 

Name: _____________________  Netid: _________________

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. The method printQ below prints one line for every node in a tree. The first value printed when called with the tree above is the string macaque. What is the complete output?
   public static void printQ(TreeNode root){ Queue<TreeNode> q = new LinkedList<TreeNode>(); if (root != null){ q.add(root); } while (q.size() != 0){ root = q.remove(); System.out.println(root.info); if (root.left != null) q.add(root.left); if (root.right != null) q.add(root.right); } }
6. The method printS below prints one line for every node in a tree. The first value printed when called with the tree above is the string macaque. What is the complete output?
   public static void printS(TreeNode root){ Stack<TreeNode> st = new Stack<TreeNode>(); if (root != null){ st.push(root); } while (st.size() != 0){ root = st.pop(); System.out.println(root.info); if (root.right != null) st.push(root.right); if (root.left != null) st.push(root.left); } }
7. The tree below is formed by copying the shape of the monkey/primate tree and storing in each node the count of how many nodes are in the subtree rooted at the node. This new tree could be created by the code shown below the diagram.

   

   The complexity of method copyCount below is not O(n) for an n-node tree. Suppose for example that every time count is called with a specific node as a parameter the node gets one cent deposited in it. The root only gets one cent deposited in it --- why? How many cents get deposited in each leaf shown? Why? If the total cost of the method copyCount includes these pennies/cents, can you provide a cost of the entire complexity using big-Oh? Assume a tree is perfectly balanced in coming up with an answer, e.g., there are two nodes below the root, four below that, eight below that, etc., with each level containing a power of two. For an N-node tree, roughly half the nodes are in the last level, how many pennies are in each of these leaf nodes? Given this as a starting point, what is the big-Oh complexity of the method copyCount below?

   public static int count(TreeNode root){ if (root == null) return 0; return 1 + count(root.left) + count(root.right); } public static TreeNode copyCount(TreeNode root){ if (root == null) return null; return new TreeNode(""+count(root),copyCount(root.left), copyCount(root.right)); }
8. You've found part of an O(n) solution to generating the tree of counts as shown in the previous problem, i.e., in which each node stores the count of the nodes in the subtree rooted at the node. The code below is part of a correct solution, you can complete it by adding lines of code. You should not delete any code already written. The completed method fastCopy should run in O(n) time for an n-node tree and should create a counted-copy as described previously. Justify that your solution is O(n) by writing a recurrence for it.
   public static TreeNode fastCopy(TreeNode root){ if (root == null) return null; root = new TreeNode("",fastCopy(root.left), fastCopy(root.right)); // do O(1) work below int lcount = 0; int rcount = 0; if (root.left != null) lcount = Integer.parseInt(root.left.info); // fill in code below return root; }