Name: ________________________________

Honor Code Acknowledgment: ___________________

Random Quiz # 6

CPS 100, Fall 1995

Due: October 31 (Boo!)

Problem 1: Annie Trees (2 points)

True or False: In every non-empty binary tree there exists a node with no parent.

Problem 2: Big Oaks (2 points)

Give a terse description of the value returned by the function Mystery shown below. 
    int Mystery(Tree * t)
    {
        if (t == NULL)
            return 0;
        else if (t->left == NULL && t->right == NULL)
            return 1;
        else
            return Mystery(t->left) + Mystery(t->right);
    }

Problem 3: Search Me (3 points)

The function below is intended to return false if its parameter is NOT a binary search tree and true if it is a search tree. It does not work as intended. Draw a tree that is not a search tree, but for which the function returns false. 
bool IsBST(Tree * t)
{
    if (t == NULL)
    {
         return true;       // empty tree is a search tree
    }
    else if (IsBST(t->left) && IsBST(t->right))
    {
            return true;
    }
    else  // not a search tree
    {
        return false;
    }
}