CSE 143, Summer 2000
Final
Programming Problem (No. 18), Sample Solutions

............................................................
Part A

various answers acceptable

We could compare the results of in-order traversals of both trees,
since they should match exactly for binary search trees with
identical content.  One easy way to do this is by using a
recursive function which stores values from the tree into an array
while performing the traversal.  This concise solution runs in
O(n) time.  O(n) for each of two traversals and O(n) for comparing
the results.

Another solution is asymptotically slower, but doesn't require
arrays.  Since neither tree contains duplicate values, if we make
sure that every value in T1 is in T2 and every value in T2 is in
T1, we can conclude the trees are content-equal.  A function
(e.g. treeContainsValue) should be used to check whether a tree
contains a value.  This function would be used by another function
(e.g. treeContainsTree), which would be called twice from
isContentEq.

Alternatively, we could make sure the tree's sizes match,
then call treeContainsTree once, but this requires
implementing a treeSize function.

Both of the above solutions run in O(n lg n) time, where n is
number of nodes in the larger of T1 and T2 and with the assumption
that the trees are balanced, i.e. have logarithmic height.


............................................................
Part B

See helper function definitions below.


// runs in O(n) time
bool isContentEq(BinTreeNode *T1, BinTreeNode *T2) 
{
  double values1[MAX_TREE_SIZE], values2[MAX_TREE_SIZE];
  int index1 = 0;
  int index2 = 0;

  inorderRetrieve(T1, values1, index1);
  inorderRetrieve(T2, values2, index2);

  if (index1 != index2) {
    return false;
  }

  for (int i = 0; i < index1; i++) {
    if (values1[i] != values2[i]) {
      return false;
    }
  }

  return true;
}


// runs in O(n lg n) time
bool isContentEq2(BinTreeNode *T1, BinTreeNode *T2)
{
  return treeContainsTree(T1, T2) && treeContainsTree(T2, T1);
}


// runs in O(n lg n) time
bool isContentEq3(BinTreeNode *T1, BinTreeNode *T2)
{
  return treeSize(T1) == treeSize(T2) && treeContainsTree(T1, T2);
}


// 
// helper functions
//

// does in-order traversal of tree rooted at r and stores values in
// array values; indexRef is (size  of tree - 1) at end
void inorderRetrieve(BinTreeNode *r, double values[], int &indexRef) {
  if (r != NULL) {
    inorderRetrieve(r->left, values, indexRef);
    values[indexRef] = r->value;
    indexRef++;
    inorderRetrieve(r->right, values, indexRef);
  }
}


// returns true iff tree rooted at r contains value key
bool treeContainsValue(BinTreeNode *r, double key)
{
  if (r == NULL) {
    return false;
  } else if (r->value == key) {
    return true;
  } else {
    return treeContainsValue(r->left, key) ||
           treeContainsValue(r->right, key);
  }
}


// returns true iff tree rooted at r1 contains all values in tree
// rooted at r2
bool treeContainsTree(BinTreeNode *r1, BinTreeNode *r2)
{
  if (r2 == NULL) {
    return true;
  } else {
    return treeContainsValue(r1, r2->value) &&
      	   treeContainsTree(r1, r2->left) &&
      	   treeContainsTree(r1, r2->right);
  }
}