Sample solutions problems on the final exam study guide

       Don't look at these until you've tried the problems first.


Given :

class node
{ int head;
  node left, right;
  public node(int h, node l, node r) {head=h; left=l; right=r;}
...

1. Write a function that returns the smallest integer in a tree
   (not binary search tree).

   Since it's not a search tree, we have to use recursion to 
   look in both the left and right branch.  The answer is the
   smallest value among the head, the smallest on the left subtree
   and the smallest on the right subtree.

   public int smallest()
   {
      int answer = head;
      int l=answer; 
      int r=answer;
      if (left!=null) l = left.smallest();
      if (l<answer) answer = l;
      if (right!=null) r = right.smallest();
      if (r<answer) answer = r;
      return answer;
   }
  
   Note the oop style of this function.  In the static style, we
   would have to decide what the "answer" is if the entire tree
   is null, such as:

   public static int smallest(node T) throws Exception
   { if (T==null) throw new Exception("undefined");
     ...



2. Write a function that returns the smallest integer in a binary
   SEARCH tree.  Do NOT use recursion.

   public int smallestBST()
   {
      node i = this;
      while (i.left!=null) { i=i.left }
      return i.head;
   }

   The smallest value in a BST is always on the extreme left node.  Remember
   That the loop should stop ON, not after, the last node, just like
   with many linked list procedures.

3. Explain the effect on tree A of the following code (draw a diagram)

   node A = new node(3, new node(2,null,null), null);
   node i = A.right;
   i = new node(4,null,null);

   (be careful - i is a pointer, and where is it pointing to?)

   A is unchanged.  i was set to point to another node, but this does
   not affect i.  i only pointed to A.right, it is not itself the same
   as A.right.


4. Implement the insert function for binary search trees:

   // look in node.java for solution


5. Given the following tree:

      9
    /   \
   5     10
  / \     \ 
 3   7     11
    / \
   6   8

Determine the order in which the nodes will be printed using a 

preorder:   9 5 3 7 6 8 10 11

inorder:    3 5 6 7 8 9 10 11

postorder traversal (post order is right-left-head).
            11 10 8 6 7 3 5 9


6. The tree in problem 5 is a binary search tree.  Draw the tree after the
   root (9) is deleted.

   We move the largest value on the left tree to the root:

      8
    /   \
   5     10
  / \     \ 
 3   7     11
    / 
   6  


7. Explain the purpose of the "Deleted" array in a closed hash table.  That
   is, why is it necessary to distinguish between a slot that was never
   occupied and a slot that's empty but was previously occupied.  

   Assume that elements A B and C all yield the same hash value.  This
   means that in a close hash table rehashing is needed to store them
   in different parts of the array.  Assume that they're initially stored in
   consecutive locations, then B was deleted.  Suppose now someone searches
   for C.  The hash/rehash procedure will first take you to position where
   B resides.  At this point, if you know that the slot was never occupied
   then you can immediately conclude that C doesn't exist.  However, if
   we have the information that the slot had a previous occupant, we must
   rehash again and search further.


8. Consider the following functions on binary trees (not nessarily search trees).  
   Which of the following functions are "naturally polymorphic", and which
   will require abstraction (in the form of abstract classes and dynamic
   dispatch).  That is, assume that the node class has been parameterized.

   class node<T>
   { T head;
     node<T> left, right;
     ...
   }

   size:  find the number of nodes in a tree.   

    Natural (never looks at head)

   depth: find the length of the longest branch.  natural

    Natural (never looks at head)

   max  : find the largest element in a general binary tree.

    Requires the meaning of ">" to be abstracted

   smax : find the largest element in binary SEARCH tree (think!).

    Natural.  The largest element in a search tree is always on
    the extreme right node (analogous to the smallest function above).
    Therefore, there's again no need to compare with the head of any node.

   
9. A tree is called "normal" if every node is either null or has both
   non-null left and right branches.  In other words, either both left and
   right are null or neither are null.  Write a procedure that checks for
   this property.

   public boolean normal()
   {
      if (left==null && right==null) return true;
      if (left==null && right!=null) return false;
      if (left!==null && right==null) return false;
      return left.normal() && right.normal();
   }

   Is this function naturally polymorphic?

   Yes.  The head is clearly never examined.

10. The binary search algorithm works well with a sorted array, and with
    binary search trees.  Explain why it doesn't work with sorted linked 
    lists.

    A critical ability of binary search is to jump to the middle
    element immediately.  In an array, this is just the middle index:
    A.length/2.  In a roughly-balanced binary search tree, the root
    node can be used for the middle node.  In a sorted list, we will
    have to traverse the tail pointers through half the list just to
    get to the middle node.  This operation already takes time
    linearly proportional - O(n) - to the length of the list,and thus
    the binary search procedure cannot possbily be O(log n).


(more may be added later ...)

11.  Consider the polymorphic cell class

class cell<A>
{
  A head;
  cell<A> tail;
  cell(A h, cell<A> t) {head=h;  tail=t; } 
  ...
}


11a.  Write code to use this class to construct a list 2 Integers.

   cell<Integer> M = new cell<Integer(3,new cell<Integer>(6,null));

11b.  Write a procedure within the class to find and return the middle
      cell of the list (this is naturally polymorphic because you
      never have to consider the head).  That is, if there are 5 elements,
      return the 3rd element.  If there are 8 elements, return the 5th
      element (the one slightly to the right of middle).  
      Naturally you'll need to find the length first.  

  public cell<A> middle()
  {
     int len = 0;  
     cell<A> i = this;
     while (i!=null) {len++; i=i.tail;} // find length
     i = this; // reset to start
     for(int j=0;j<len/2;j++) { i = i.tail; }  // get to the middle
     return i;
  }