Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys. (Both low key and high key do not have to be a key on the list).

BST.java

import java.lang.Comparable;

/** Binary Search Tree implementation for Dictionary ADT */ class BST, E> implements Dictionary { private BSTNode root; // Root of the BST int nodecount; // Number of nodes in the BST

/** Constructor */ BST() { root = null; nodecount = 0; }

/** Reinitialize tree */ public void clear() { root = null; nodecount = 0; }

/** Insert a record into the tree. @param k Key value of the record. @param e The record to insert. */ public void insert(Key k, E e) { root = inserthelp(root, k, e); nodecount++; }

// Return root

public BSTNode getRoot() { return root; }

/** Remove a record from the tree. @param k Key value of record to remove. @return The record removed, null if there is none. */ public E remove(Key k) { E temp = findhelp(root, k); // First find it if (temp != null) { root = removehelp(root, k); // Now remove it nodecount--; } return temp; }

/** Remove and return the root node from the dictionary. @return The record removed, null if tree is empty. */ public E removeAny() { if (root == null) return null; E temp = root.element(); root = removehelp(root, root.key()); nodecount--; return temp; }

/** @return Record with key value k, null if none exist. @param k The key value to find. */ public E find(Key k) { return findhelp(root, k); }

/** @return The number of records in the dictionary. */ public int size() { return nodecount; } private E findhelp(BSTNode rt, Key k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) return findhelp(rt.left(), k); else if (rt.key().compareTo(k) == 0) return rt.element(); else return findhelp(rt.right(), k); } /** @return The current subtree, modified to contain the new item */ private BSTNode inserthelp(BSTNode rt, Key k, E e) { if (rt == null) return new BSTNode(k, e); if (rt.key().compareTo(k) > 0) rt.setLeft(inserthelp(rt.left(), k, e)); else rt.setRight(inserthelp(rt.right(), k, e)); return rt; } /** Remove a node with key value k @return The tree with the node removed */ private BSTNode removehelp(BSTNode rt,Key k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) rt.setLeft(removehelp(rt.left(), k)); else if (rt.key().compareTo(k) < 0) rt.setRight(removehelp(rt.right(), k)); else { // Found it if (rt.left() == null) return rt.right(); else if (rt.right() == null) return rt.left(); else { // Two children BSTNode temp = getmin(rt.right()); rt.setElement(temp.element()); rt.setKey(temp.key()); rt.setRight(deletemin(rt.right())); } } return rt; }

private BSTNode getmin(BSTNode rt) { if (rt.left() == null) return rt; return getmin(rt.left()); }

private BSTNode deletemin(BSTNode rt) { if (rt.left() == null) return rt.right(); rt.setLeft(deletemin(rt.left())); return rt; } private void printhelp(BSTNode rt) { if (rt == null) return; printhelp(rt.left()); printVisit(rt.element()); printhelp(rt.right()); }

private StringBuffer out;

public String toString() { out = new StringBuffer(400); printhelp(root); return out.toString(); } private void printVisit(E it) { out.append(it + " "); }

}

BSTNode.java

class BSTNode implements BinNode { private Key key; // Key for this node private E element; // Element for this node private BSTNode left; // Pointer to left child private BSTNode right; // Pointer to right child

/** Constructors */ public BSTNode() {left = right = null; } public BSTNode(Key k, E val) { left = right = null; key = k; element = val; } public BSTNode(Key k, E val, BSTNode l, BSTNode r) { left = l; right = r; key = k; element = val; }

/** Get and set the key value */ public Key key() { return key; } public void setKey(Key k) { key = k; }

/** Get and set the element value */ public E element() { return element; } public void setElement(E v) { element = v; }

/** Get and set the left child */ public BSTNode left() { return left; } public void setLeft(BSTNode p) { left = p; }

/** Get and set the right child */ public BSTNode right() { return right; } public void setRight(BSTNode p) { right = p; }

/** @return True if a leaf node, false otherwise */ public boolean isLeaf() { return (left == null) && (right == null); } }

BinNode.java

/** ADT for binary tree nodes */ public interface BinNode { /** Get and set the element value */ public E element(); public void setElement(E v);

/** @return The left child */ public BinNode left();

/** @return The right child */ public BinNode right();

/** @return True if a leaf node, false otherwise */ public boolean isLeaf(); }