Spellcheck

A basic spell checker backed by a binary search tree. You must provide missing BST implementation to make the spell checker function correctly!

Preliminaries

• src/main/java/Spellcheck.java contains the main spell checker. Read over this code to familiarize yourself with how the spell checker works.

• src/main/java/BstMap.java contains a dictionary ADT backed by a binary search tree. Note the inner Node class is missing implementations for insert, find, and remove. Familiarize yourself with the code in this file.

• Note that keys in BstMap are required to implement the Comparable<T> interface. Recall that this interface provides a compareTo(T other) method such that:

  1. x.compareTo(y) == 0 if x == y
  2. x.compareTo(y) < 0 if x < y
  3. x.compareTo(y) > 0 if x > y

Exercises

1. Implement BstMap.Node.find(...).

2. Implement BstMap.Node.insert(...).

3. The spell checker should function with only find and insert are implemented. Test it:

   cd src/main/java
   javac Spellcheck.java && java Spellcheck "It was the best of times, it was the blurst of times."

   What did you observe? If your implementation failed to report a result or triggered a stack overflow error, why do you think this happened?

4. If your test from exercise 3 did not work properly, identify and implement a fix. If it did work properly, print the tree structure to a depth of 20 using BstMap.Node.printKeys(...). What do you notice about the structure?

5. What is the big-O of find and insert in the worst case? In the average case?

6. (If time allows) Implement BstMap.Node.remove(...). Test your implementation by removing words from the dictionary and verifying the appropriate misspellings are reported.