CPS 100, Spring 2004, Recitation Feb 16-17

Use the declaration for tree nodes given below for each of the questions. struct TreeNode { string info; TreeNode * left, * right; TreeNode (const string& s, TreeNode * lptr, TreeNode * rptr) : info(s), left(lptr), right(rptr) { } };

You may find these recurrences and solutions useful in answering questions.

Recurrence Solution
T(n) = T(n/2) + O(1) O(log n)
T(n) = T(n/2) + O(n) O(n)
T(n) = 2T(n/2) + O(1) O(n)
T(n) = 2T(n/2) + O(n) O(n log n)
T(n) = T(n-1) + O(1) O(n)
T(n) = T(n-1) + O(n) O(n2)

  1. Solve the following recurrence: T(n) = 4T(n/2) + 1
    T(1) = O(1)
    T(0) = O(1)
  2. The function deepLeaf below returns a pointer to the deepest leaf in a tree (furthest from the root).

    bool isLeaf (TreeNode * t) // post: returns true iff both children of t are null { if (t == 0) return false; else return (t->left == 0) && (t->right == 0); } TreeNode * deepLeaf(TreeNode * t) // post: returns pointer to deepest leaf in t { if (t == 0) return 0; else if (isLeaf(t)) return t; if (height(t->left) >= height(t->right)) { return deepLeaf(t->left); } else { return deepLeaf(t->right); } }

    1. Describe in a few sentences the logic behind how deepLeaf works. Note that only one recursive call is made from the body of deepLeaf, but that in a sequence of recursive calls (from the original call with the root of a tree) one leaf node is ultimately identified as the leaf, that is only one node will satisfy isLeaf(t) in the code above. How does this work?
    2. Write a recurrence relation for deepLeaf in the average case when trees are roughly balanced. Note that there is only one recursive call made because of the conditional statements. What is the big-Oh solution to this recurrence?
    3. Consider the worst case for deepLeaf. For example, a tree of n nodes in which every non-leaf node has no left child and one right child. Write a recurrence for deepLeaf in this worst case. What is the solution to the recurrence?
    4. You should see from the previous problem that the version of deepLeaf above is not O(n) in the worst case. For this problem you will write a new version that will be O(n). The code above calls height and makes recursive calls, so it visits many nodes more than once. We need to determine the height and deepest leaf at every node, that's two quantities. Instead of using two functions, complete the function below so it satisfies its postcondition and so that its recurrence in the average (balanced tree) case is:
        T(n) = 2T(n/2) + O(1)
        T(0) = O(1)
      Use the comments to guide you in writing the function and see the code for balanceHelper above.

      TreeNode * deepHelper(TreeNode * t, int& height)
      // post: (return via reference) height = height of tree rooted at t
      //       returns pointer to deepest leaf in t
          if (t == 0) {     // could happen, be safe
              height = 0;
              return 0;
          if (isLeaf(t)) {  // I'm a leaf return myself and my height
                            // fill in values here
                            // fill in values here 
          // define int variables for heights via recursive calls 
          // define Tree pointers for leaves via recursive calls
          // make two recursive calls
          // set height = 1 + max of two recursive call values
          // using computed heights, determine which leaf to return
      TreeNode * deepLeaf(TreeNode * t)
      // post: return deepest leaf in t
          int height;
          return deepHelper(t, height);

Jeff Forbes
Last modified: Fri Feb 13 19:48:19 EST 2004