JAVA - Part A and B - *USE HINTS GIVEN TO MAKE THE CODE* (Please help I will give thumbs up if it works. Thanks you!!)

HINTS:

BST.java [starter code] - use for PART A

import java.util.ArrayList;

/** BST implementation for Dictionary ADT */ class BST, E> implements Dictionary { private BSTNode root; // Root of BST private int nodecount; // Size of 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(K k, E e) { root = inserthelp(root, k, e); nodecount++; }

/** * Remove a record from the tree. * * @param k * Key value of record to remove. * @return Record removed, or null if there is none. */ public E remove(K k) { E temp = findhelp(root, k); // find it if (temp != null) { root = removehelp(root, k); // remove it // System.out.println("called removehelp"); nodecount--; } return temp; }

/** * Remove/return root node from dictionary. * * @return The record removed, null if 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 k, null if none. * @param k * The key value to find. */ public E find(K k) { return findhelp(root, k); }

/** @return Number of records in dictionary. */ public int size() { return nodecount; }

private E findhelp(BSTNode rt, K 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); }

private BSTNode inserthelp(BSTNode rt, K 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; }

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

private BSTNode deletemin(BSTNode rt) { if (rt.left() == null) return rt.right();

else { rt.setLeft(deletemin(rt.left())); return rt; } }

/** * Remove a node with key value k * * @return The tree with the node removed */ private BSTNode removehelp(BSTNode rt, K k) { if (rt == null) return null; if (rt.key().compareTo(k) > 0) rt.setLeft(removehelp(rt.left(), k)); else if (rt.key().compareTo(k) temp = getmin(rt.right()); rt.setElement(temp.element()); rt.setKey(temp.key()); rt.setRight(deletemin(rt.right())); } } return rt; }

/** * Creates a list storing the the nodes in the subtree of a node, ordered * according to the inorder traversal of the subtree. */

protected void inorderElements(BSTNode v, ArrayList elts) { // elts.add(v.element()); if (v.left() != null) inorderElements(v.left(), elts); // recurse on left child elts.add(v.element()); if (v.right() != null) inorderElements(v.right(), elts); // recurse on right child }

/** Returns an iterable collection of the tree nodes. */ public Iterable values() { ArrayList elements = new ArrayList(); if (size() != 0) inorderElements(root, elements); // assign positions in order return elements; }

public Iterable findAll(K k) { ArrayList al = new ArrayList(); findAllhelp(root, k, al); return al; }

protected void findAllhelp(BSTNode rt, K k, ArrayList a) { if (rt == null) return; if (rt.key().compareTo(k) > 0) findAllhelp(rt.left(), k, a); else if (rt.key().compareTo(k) == 0) { a.add(rt.element()); findAllhelp(rt.right(), k, a); } else findAllhelp(rt.right(), k, a); }

/* the following are for solving the exercises in Shaffer, ch. 5 */

public Iterable range(K a, K b) { ArrayList elements = new ArrayList(); rangehelp(root, elements, a, b); return elements; }

protected void rangehelp(BSTNode v, ArrayList elts, K a, K b) { // insert implementation } }

PrintRange.java [starter code] -- use for PART B

import java.io.File; import java.io.FileNotFoundException; import java.util.Scanner; import java.util.ArrayList;

/* * Print out all dictionary records in a given range of keys. */ public class PrintRange {

public static void main(String[] args) { BST PDict = new BST(); File file = new File("shuffledDictionary.txt");

// Read in the (shuffled) cmu pronunciation dictionary. try { Scanner scanner = new Scanner(file); while (scanner.hasNextLine()) { String line = scanner.nextLine(); if (line.substring(0, 3).equals(";;;")) continue; // skip comment lines Pronunciation p = new Pronunciation(line); PDict.insert(p.getWord(), p); // key dictionary on word } scanner.close(); } catch (FileNotFoundException e) { e.printStackTrace(); }

Scanner input = new Scanner(System.in); String a = input.next(); // first word in range String b = input.next(); // last word in range for(Pronunciation p : PDict.range(a,b)) System.out.println(p.getWord()+" "+p.getPhonemes()); } }

(a) Add a method levelorder Elements() to the BST.java binary search tree dictionary implementation on Vocareum. In level order the root comes first, then all nodes of level 1, then all nodes of level 2, and so on. Within a level, the order is left to right; i.c., in ascending order. Model your method on inorder Elements(). Test your method by changing the calls to inorderElements() in values() to levelorder Elements(). This way, values() will return the values in the dictionary in level order. Hint: Preorder traversals make use of a stack through recursive calls. Consider making use of another data structure to help implement the levelorder traversal. (b) The BST class has a method range() with the following declaration: public Iterable range (Ka, Kb) Passed a low key value a and a high key value b, range should return an ArrayList that contains all the dictionary values with key between a and b, inclusive, in order. The range method relies on the rangehelp method, which is not fully implemented. Complete the definition of rangehelp. Use the program Print Range.java to test your method. It reads in the shuffled cmu pronunciation dictionary and creates a dictionary keyed on word. The program reads two strings from the terminal, and prints out all records with keys that fall between the two given strings, inclusive. Your range method should visit as few nodes in the BST as possible. For example, with input DOFF DOG PrintRange should produce the output DOFF D A01 F DOFFING DA01 F IHO NG DOFFS D 101 F S DOG D A01 G Scoring: The score will be based on correct output and efficient implemen- tation. There will be four test cases in total, two cach for part (a) and part (b). Running time should be under 10 seconds. Hint levelorderElements(root, arraylist) Use queue (linked list) Add root to the queue Add value at root to the arraylist While (queue is not empty): current node = dequeuel) if current node has left child: add left child to queue add value at left child to arraylist if current node has right child: add right child to queue add value at right child to arraylist Hint 2 rangehelp(root, arraylist, low key, high key), return an ArrayList that contains all the dictionary values with key between 2 keys, in order Check if root is null If root.key > low key: rangehelp(left child of root, arraylist, low key, high key); If root.key >= low key and root.key