CSE 143, Quiz 10                                                    15 Aug 2000

name ____________________________________________ student number _______________

                                                              section __________

This quiz is closed book, closed notes.  You have six minutes.  Write your
answers neatly on this page.

Assume type BinTreeNode (binary tree node) is defined as follows:

  struct BinTreeNode {
    int item;
    BinTreeNode *left, *right;
  };

For each functions below, choose the correct description of the function's
purpose, i.e. what the function computes and returns, and give its asymptotic
running time (in terms of n, where n is the number of items in the tree):

1.  int mystery(BinTreeNode *r) {
      if (r == NULL) {
        return 0;
      } else {
        return 1 + mystery(r->left) + mystery(r->right);
      }
    }

    function's purpose (Circle one letter.):

      a.  returns the sum of the items in the subtree rooted at r
      b.  returns the product of the items in the subtree rooted at r
      c.  returns the largest item in the subtree rooted at r
      d.  returns the smallest item in the subtree rooted at r
      e.  returns the height of the subtree rooted at r
      f.  returns the number of items in the subtree rooted at r
      g.  returns the number of leaf nodes in the subtree rooted at r

    function's asymptotic running time:  O(_______________)


2.  int anotherMystery(BinTreeNode *r) {
      if (r == NULL) {
        return 0;
      } else {
        return r->item + anotherMystery(r->left) + anotherMystery(r->right);
      }
    }

    function's purpose (Circle one letter.):

      a.  returns the sum of the items in the subtree rooted at r
      b.  returns the product of the items in the subtree rooted at r
      c.  returns the largest item in the subtree rooted at r
      d.  returns the smallest item in the subtree rooted at r
      e.  returns the height of the subtree rooted at r
      f.  returns the number of items in the subtree rooted at r
      g.  returns the number of leaf nodes in the subtree rooted at r

    function's asymptotic running time:  O(_______________)

................................................................................

1.  f.
    O(n); O(1) work per call, one call per node, O(n) nodes

2.  a.
    O(n)