Home CPSC 340

Assignment 6 - Spell Checker

Due: April 19


To gain experience using templates and binary search trees.


A simple way of performing spell checking is to store the set of all valid words in some data structure. For each word we need to check, we'll search the data structure to see if the word is stored. If it is, we will say that the word is spelled correctly. If not, we will say that the word is spelled incorrectly.

For this assignment, you will be writing a program that does spell checking with a binary search tree.

Your program will take a command-line parameter which will be the name of a dictionary file. This file will contain every word that your program should consider to be correctly spelled. If the user doesn't specify the name of the dictionary file, or if the file doesn't exist, your program should print an error message.

Here is a sample dictionary file. This file contains almost 100,000 English words.

Your program should open the dictionary file and insert the words, one by one, into a binary search tree. Then your program should take input from the user and report whether or not each word they enter is spelled correctly or not. The word "END" will signify the end of input.

The program's efficiency will depend on how balanced the tree is, so you should print out the height of the tree after inserting all of the words from the dictionary. You do not need to balance the tree, you can just insert them in the order they are in the file. If you insert the file above using the insertion algorithm discussed in class, the height should be 42.

Here is a sample run of such a program:

$ spellcheck words.txt 
Loaded the words into a tree with height = 42
this is a test
Missisippi is spelled wrong!
here are some moar words 
moar is spelled wrong!


General Requirements


Submit your program by emailing your source files to ifinlay@umw.edu.

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.