// methods of the dictionary ADT
  public int size() { return numEntries; }
  public boolean isEmpty() { return size() == 0; }
  public Entry find(Object key) throws InvalidKeyException {
    checkKey(key);		// may throw an InvalidKeyException
    Position curPos = treeSearch(key, root());
    actionPos = curPos;		// node where the search ended
    if (isInternal(curPos)) return entry(curPos);
    return null;
  public Iterator findAll(Object key) throws InvalidKeyException {
    checkKey(key);		// may throw an InvalidKeyException
    List L = new NodeList();
    addAll(L, root(), key);
    return L.elements();
  public Entry insert(Object k, Object x) throws InvalidKeyException {
    checkKey(k);	// may throw an InvalidKeyException
    Position insPos = treeSearch(k, root());
    while (!isExternal(insPos))  // iterative search for insertion position
      insPos = treeSearch(k, left(insPos));
    actionPos = insPos;	// node where the new entry is being inserted
    return insertAtExternal(insPos, new BSTEntry(k, x, insPos));
  public Entry remove(Entry ent) throws InvalidEntryException  {
    checkEntry(ent);            // may throw an InvalidEntryException
    Position remPos = ((BSTEntry) ent).position(); 
    Entry toReturn = entry(remPos);	// entry to be returned
    if (isExternal(left(remPos))) remPos = left(remPos);  // left easy case
    else if (isExternal(right(remPos))) remPos = right(remPos); // right easy case
    else {			//  entry is at a node with internal children
      Position swapPos = remPos;	// find node for moving entry
      remPos = right(swapPos);
	remPos = left(remPos);
      while (isInternal(remPos));
      replaceEntry(swapPos, (Entry) parent(remPos).element());
    actionPos = sibling(remPos);	// sibling of the leaf to be removed
    return toReturn;
} 	// entries() method is omitted here