Extra Test/Written Work, CPS 100

Owen Astrachan, Robert Duvall, Jeff Forbes

April 19, 2001

Login:

Honor code acknowledgment (signature)

You can use any books, notes, or internet web-pages. You cannot talk to any person either live or via chat etc.

Due at the beginning of class on Wednesday, no extensions

The declaration for binary search tree nodes on this test is:

struct TreeNode
{
  string info;
  TreeNode * left;
  TreeNode * right;

  TreeNode(const string& s, TreeNode * lt, TreeNode * rt)
    : info(s), left(lt), right(rt)
  { }
};

PROBLEM 1 :   (Family Trees)
In this problem assume all values in trees are unique, no value appears more than once in a tree.

The code in the function leastAncestor shown below returns a pointer to the least ancestor of two strings in a tree.

The least ancestor of two string values p and q is the node furthest from the root (deepest) which is an ancestor of both p and q (there is a path from the least ancestor to both p and q).

For example, the tree diagrammed below on the right yields the values shown in the table on the left.

p	q	least ancestor
F	E	B
C	G	B
K	H	C
H	J	A
A	G	A
G	A	A

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

Tree * leastAncestor(Tree * t, const string& p, const string& q)
// post: returns pointer to least ancestor of p and q in t
//       returns null if one/both of p/q not in tree t    
{
    if (t == 0) return 0;

    // first check subtrees (lower than me) for ancestor
    Tree * result = leastAncestor(t->left, p,q);
    if (result != 0) return result;
    
    result = leastAncestor(t->right,p,q);
    if (result != 0) return result;

    // didn't find in subtrees, am I the least ancestor? check
    if ( (t->info == p || inTree(t->left,p))  && (t->info == q || inTree(t->right,q))) {
        return t;
    }
    if ( (t->info == q || inTree(t->left,q))  && (t->info == p || inTree(t->right,p))) {
        return t;
    }

    return 0;
}

The complexity of leastAncestor is not O(n) for an n-node tree. What is the complexity and why? Justify using recurrence relations and an explanation of each part of the recurrence.

Part B (6 points)

Write the function path whose header is given below. The function sets values in/returns a vector representing the path from the root of t to the node containing target if there is a path, or returns an empty vector otherwise.

For example, given the tree on the previous page we have:

void path(Tree * t, const string& target, tvector<string>& v)
// pre: v initially empty (on first call to path)
// post: v represents path of global-root of t to target
//       otherwise v.size() == 0 if target not in t
{

}

Write a version of leastAncestor that runs in O(n) time for an n-node tree. You can use any approach; one approach is to use the function path from part B, another is to write an auxiliary function that returns three values via reference parameters from a tree: an ancestor-pointer and a bool that tells if p is in the tree and a bool that tells if q is in the tree.

Write the code and justify that it runs in O(n) time.

PROBLEM 2 :   (Heaps of Trouble (7 points))
Complete the function lessCount to determine the number of elements in a minheap that are less than a target number. A minheap is a heap such that the value in each node is less than the value in the node's subtrees. A min heap is implemented via a vector with the root at index 1 as we discussed in class.

In the example below, lessCount(heap,13) should return 3 (6, 8, and 10 are less than 13), and lessCount(heap,8) should return 1 (only 6 is less than 8).

int lessCount(const tvector<int> & heap, int target)
// pre:  heap is a minheap containing heap.size() elements          
// post: returns the number of elements in the heap
//       less than target
{





}

int lessAux(const tvector<int> & heap, int index, int target)
// pre:  heap is a minheap with heap.size() elements
//       1 <= index < heap.size()
// post: returns # elements in subheap rooted/starting at index
//       that are less than target
{

}