CPS 100, Spring 2004, Recitation Feb 16-17

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

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);
      }