PLEASE DO NOT POST ANY OLD CODE NOR HARD CODE ANYTHING.

IF YOU DO NOT KNOW HOW TO ANSWER TRANSFER IT TO SOMEOnE WHO DOES.

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(); }