Other 2004 FR Questions FR other years Be Prepared Home
AB-4
Part (a)
  // precondition:  the priority queue is not empty
  // postcondition: a data value of smallest priority is returned;
  //                the priority queue is unchanged
  public Object peekMin()
  {
    if (root == null)
      throw new NoSuchElementException(); 1

    TreeNode t = root;

    while(t.getLeft() != null) 2
      t = t.getLeft();

    return ((Item)t.getValue()).getData(); 3
  }
Notes:
  1. This check is optional because the precondition states that the queue is not empty.  But, strictly speaking, the precondition here contradicts the description of the peekMin method in the PriorityQueue interface.

  2. The smallest value in a BST is in its leftmost node.  It is easier to find that node using iterations, rather than recursion.

  3. Not
        return t.getValue();
    You need the cast to Item to call getData.

Part (b)
  // postcondition: obj has been added to the subtree rooted at t;
  //                the resulting subtree is returned
  private TreeNode addHelper(Comparable obj, TreeNode t)
  {
    if (t == null)
      return new TreeNode(new Item(obj)); 1

    Item item = (Item)t.getValue();
    int diff = obj.compareTo(item.getData());
    if (diff == 0)
      item.incrementCount();
    else if (diff < 0)
      t.setLeft(addHelper(obj, t.getLeft())); 2
    else // if (diff > 0)
      t.setRight(addHelper(obj, t.getRight()));

    return t;
  }
Notes:
  1. Not
          return new TreeNode(obj);
  2. It is important to not just call addHelper, but also append the tree returned by it to the parent node.

Other 2004 FR Questions | Back to Contents

Copyright © 2004 by Skylight Publishing
support@skylit.com