Efficient Dictionary

Project description

Your task is to create an application for efficiently storing words in a dictionary and efficiently answering queries over said dictionary.

It is important to understand that the application will constantly receive data. For example, the user may add some words, perform some queries, add more words, perform some more queries, and so on. Therefore, using an array to solve the problem and constantly sorting or checking all the elements to answer a query every time will be too slow. One of the main requirements is that the application must be fast and responsive. To address this point, you use your handy binary search tree implementation.

Automatic testing

The tasks will be tested automatically based on the messages displayed from your functions. Make sure not to have any typos, extra spaces, or newlines (or missing spaces or newlines) inside the messages, or the tests will fail.

Note: If some tests fail and you want to perform some debugging, feel free to display the tree using the printBST function. Just know that as soon as you do this, the tests will fail because the output will not match. It is fine, but don’t forget to remove the debug messages after you fix the bugs. Otherwise, the tests will still not work.

Note: If the tree is big, the output of printBST may break, as there is not enough space in the console to display the whole tree.

Finally, for testing purposes, the tester will do the following:

• It will call the testStarted function before performing any tests. It allows you to perform any initializations if you need them. It is acceptable to leave this function empty.
• It will call the testEnded function after performing the last test. It allows you to perform any cleanup and free the memory.

Check the console to see the output of your code.

Solution

Here is a complete solution. Please check the reference solution only as a last resort after you did your best to solve the tasks on your own.