CPS 100, Spring 2004, Written Tree Assignment

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.

You should submit a file whose name must be tree.cpp, and a README file that indicates how long you spent on these problems and with whom you consulted. You are to submit solutions to these problems using

   submit_cps100 trees tree.cpp README

The solutions are in the file tree.cpp so that you can have your code formatted automatically (e.g., if you use emacs/Eclipse). You should NOT make your solutions run, you're just typing solutions to make them easier to read and to allow for electronic submission. It is important to think about your answers, not to run them.


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. struct TreeNode { string info; TreeNode * left; TreeNode * right; TreeNode * parent; TreeNode (int val, TreeNode * lt, TreeNode * rt, TreeNode * p) : info(val), left(lt), right(rt), parent(p) { } };
  1. Binary Search Tree Iterator
    1. Write functions that return the minimum and maximum nodes in a binary search tree rooted at t. Assume trees store unique elements (no duplicates). Provide a big-Oh expression for the complexity of the functions you write, assuming trees are roughly balanced (depth = log(n) for n nodes).
      TreeNode* minimum(TreeNode * t)
      // pre: t is a search tree
      // post: returns pointer to node with minimum key (NULL/0 if t is empty)
      
      
      TreeNode* maximum(TreeNode * t)
      // pre: t is a search tree
      // post: returns pointer to node with maximum key (NULL/0 if t is empty)
      
    2. Write a function to find the inorder successor of a node. You should use the parent link and the minimum function (assume minimum works as specified). This function can be written in fewer than 10 lines of code --- that's a guideline, not a requirement.
      TreeNode* successor(TreeNode * t)
      // pre: t is a search tree
      // post: returns next node in inorder traversal of tree, returns NULL/0 if
      //       t is has no inorder successor (i.e., is maximal element)
      
    3. The following code results in an inorder traversal of a tree from the root
       void inOrder(TreeNode *root)
       {
         for (TreeNode *t = minimum(root); t != 0; t = successor(t)){
            cout << t->info << endl;
         }
       }
      
      What is the big-Oh of inOrder in the worst case? Justify your answer briefly


  2. Write the function 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). If the level isn't zero, recursive calls will be used to determine the number of nodes at the requested level.

    int levelCount(TreeNode * t, int level) // pre: 0 <= level // post: returns # nodes at specified level in t


  3. In the next two problems assume trees store int values rather than string values

    1. Write the function findKthInOrder whose header is given below. Given an integer k and a binary search tree with unique values, findKthInOrder returns a 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 pointer to the node with value 9, findKthInOrder(t,8) returns a pointer to the node with value 18, and findKthInOrder(t,12) returns NULL/0 since there are only 9 nodes in the tree.

      *

      You may find it useful to call the function count discussed in lecture that returns the number of nodes in a tree.

      int count(TreeNode * t) // post: returns # nodes in t { if (t == 0) return 0; return 1 + count(t->left) + count(t->right); } TreeNode * findKthInOrder(TreeNode * t, int k) // pre: t is a binary search tree with unique values // post: returns pointer to the kth node in sorted order, // returns NULL if t has fewer than k nodes.
    2. Assuming trees are roughly balanced (e.g., average case), write a recurrence for your solution to findKthInOrder and give the solution to the recurrence.

    3. Write a recurrence for your solution to findKthInOrder for the worst case, i.e., when a tree is completely unbalanced and the function is called to do the most work on every recursive call. What is the solution to this recurrence?


  4. 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 (assuming the existence of a standard O(1) max function that returns the larger of two values).

    int diameter(TreeNode * t) // post: returns diameter of t { if (t == 0) return 0; int leftD = diameter(t->left); int rightD = diameter(t->right); int rootD = height(t->left) + height(t->right) + 1; return max(rootD, max(leftD, rightD)); }

    1. However, the function 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 function should use an auxiliary/helper function as described below. The helper function should make two recursive calls and do O(1) other work.

      int diameterHelper (TreeNode * t, int & height) // pre: t is a binary tree // post: return (via reference param) height = height of t // return as value of function: diameter of t { // write this } int diameter(TreeNode * t) // post: returns diameter of t { int height; return diameterHelper(t, height); }


  5. 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 function 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 function 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.

    bool isIsomorphic(TreeNode * s, TreeNode * t) // post: returns true if s is isomorphic to t, else returns false
  6. 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 function 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 function 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.

    bool isQuasiIsomorphic(TreeNode * s, TreeNode * t) // post: returns true if s is quasi-isomorphic to t, else returns false

Owen L. Astrachan
Last modified: Fri Feb 27 10:17:49 EST 2004