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)