Name:__________________________________                        18 October 1999

                          CS 503 Midterm Examination

                                 K. R. Kaplan

There are four questions on this exam. All work should go on this exam paper.


1.  A  binary  tree  representing  a  forest  of  general trees has a postorder
sequence HMORLSITGA and an  inorder  sequence  HOMLRASIGT.  Sketch  the  forest
represented by the tree in the space below.



















Build a simple BST by processing the single-character keys COMPLEXITY from left
to right. Compute the average cost of successful retrieval (measured in  number
of treeSearch key comparisons); compute the average cost of a failed search.



2. Using the standard class definitions for BtNode objects (char key, BtNode L,
R) and for BinTree objects  (BtNode  root)),  complete  the  BtNode  method  HT
(below)  to  compute  the  height of a binary tree. The height of a tree is the
length of a longest path from root to a leaf. Recall  that  the  height  of  an
empty tree is taken as -1.

               // a class binTree method
               public int HT(){
                  return HT(root);
               }

               // a class btNode method
               public static int HT(btNode p){
                  int LH, RH;  // heights of L, R subtrees rooted at this node
                  if(p == null) __________
                  else {










                  }
               }

A  height-balanced  binary  tree is one where the left and right subtree of any
node differ in height by no  more  than  one.  That  is,  every  subtree  is  a
height-balanced  binary  tree.  Complete  the BtNode method below which returns
true for height-balanced trees, else false.

              public boolean HB() {
                  return HB(root);
              }

              public static boolean HB(btNode p){
                  if(p == null) return true;
                  else{













                 }
              }



3. Complete the code below to find the  preorder  successor  of  a  node  in  a
right-threaded  binary  tree.  (Only  null right pointers have been replaced by
non-null threads to the inorder successor).

                 class TBinTree {
                    TBtNode root;

                    // methods
                 }

                 class TBtNode {
                    char key;
                    TBtNode L, R;
                    boolean RTH;

                    // methods

                    public static TBtNode nextInPreOrder(TBtNode n){












                    }
                  }

Describe how to use inorder  threads  to  find  the  parent  of  a  node  in  a
right-threaded binary tree.



4.  A  single-linked list class (SLL) is described below. The SLL uses a "dummy
header" (a "sentinel") element. Complete the code below for  the  join  method:
remember that the resulting SLL must conform to the class definition.

      public class ListElement {
          private Object data;
          private ListElement next;

          /* getters and setters: Object getData(), void setData(Object d),
             ListElement getNext(), void setNext(ListElement e) */
      }

      public class SLL{
        protected ListElement head;

        public SLL {
           head = new ListElement();  // constructor
        }

        public static SLL join(SLL first, SLL second){
        /* links the second list to the end of the first; returns the
           composite list */















        }
      }

If  the  first  list has n elements, and the second has m, what is the order of
the running time of this method?




How would you modify the SLL class so that join can  be  accomplished  in  unit
cost? Explain.