Test 2 Booster, CPS 100, Fall 1995

You MUST work alone on these problems. You may consult your book and your notes. These problems are due ON PAPER at the beginning of class on Tuesday, December 5. If you aren't in class you MUST turn the problems in before class, no papers will be accepted after class. For these problems trees contain strings (but this doesn't really matter).

Problem 1: (5 points)

Two binary search trees s and t are value equal if every value in s is in t and every value in t is in s. The shapes of the trees don't matter, the collection of values stored in s must be the same as the collection stored in t for trees to be value equal.

Part A

Consider the functions below. What is the big-Oh running time of IsValueEqual in the average case. Assume that both s and t contain N nodes. You MUST justify your answer (with a recurrence relation/solution or by reasoning and explanation) for credit.


bool InTree(const string & s, Tree * t)
// postcondition: returns true if s in t, otherwise returns false
{
   if (t != 0)
   {
       if (t->info == s) return true;
       return InTree(s, t->left) || InTree(s, t->right);
   }
   return false;
}

bool FirstInSecond(Tree * s, Tree * t)
// postcondition: returns true if all values of s are in t
//                returns false otherwise
{
    if (s != 0)
    {
	if (InTree(s->info,t))
	{
	    return FirstInSecond(s->left,t)  &&
		   FirstInSecond(s->right,t);
	}
	return false;
    }
    return true;
}

bool IsValueEqual(Tree * s, Tree * t)
// postcondition: returns true if s is value equal to t, 
//                returns false otherwise
{
    return FirstInSecond(s,t) && FirstInSecond(t,s);
}

Part B

Describe an O(N) algorithm for determining if two trees are value equal. If your answer to Part A is O(N), just write "see Part A".

Problem 2: (5 points)

Two binary trees s and t are equivalent if they have the same shape; the values stored in the nodes do not affect whether two trees are equivalent. In the diagram below, the tree in the middle is NOT equivalent to the other trees, but the tree on the right IS equivalent to the tree on the left.

Write a function IsEquivalent that returns true if its two tree parameters are equivalent and false otherwise. You must also give the big-Oh running time of your function with a justification.

Problem 3 (5 points)

Two trees s and t are isomorphic if s can be transformed into t by swapping left and right children of some of the nodes of s. The values in the nodes are NOT not important in determining isomorphism, only the shape is important. The trees below are isomorphic because if the children of the nodes A, B, and G in the tree on the left are swapped, the tree on the right is obtained.

Write a function IsIsomorphic that returns true if two trees are isomorphic. You must give the big-Oh complexity (in the average case) of your function with a justification.