================================================================================
         DATA STRUCTURES AND ALGORITHMS
         ASSIGNMENT 8: Dictionary & Spell Checker Using BST
         State University of Zanzibar (SUZA)
================================================================================

ANTI-PLAGIARISM NOTICE:
This assignment requires LIVE DEMONSTRATION (viva). You must:
1. Explain every function in your code
2. Modify your code on the spot when asked
3. Answer questions about your design choices
4. Submit a HANDWRITTEN design document
AI-generated or copied code will result in ZERO marks.

================================================================================
PROJECT DESCRIPTION
================================================================================

Build a dictionary and spell checker using a Binary Search Tree (BST).
Words are stored alphabetically in the BST, enabling fast lookup,
auto-complete suggestions, and spell checking.

================================================================================
REQUIREMENTS
================================================================================

DATA STRUCTURES:
   struct DictNode {
       char word[50];
       char meaning[200];      // definition of the word
       struct DictNode *left, *right;
   };

OPERATIONS TO IMPLEMENT:

1. Insert Word
   struct DictNode* insertWord(struct DictNode *root, char word[], char meaning[]);
   - Insert word maintaining BST alphabetical order (use strcmp)
   - If word exists, update the meaning

2. Search Word
   struct DictNode* searchWord(struct DictNode *root, char word[]);
   - Return pointer to node if found, NULL otherwise
   - Display the word and its meaning

3. Delete Word
   struct DictNode* deleteWord(struct DictNode *root, char word[]);
   - Handle all three BST deletion cases
   - Use inorder successor (alphabetically next word)

4. Display Dictionary
   void displayAll(struct DictNode *root);
   - Print all words in alphabetical order (inorder traversal)
   - Format: word : meaning

5. Auto-Complete (Prefix Search)
   void autoComplete(struct DictNode *root, char prefix[]);
   - Find all words starting with given prefix
   - Display them in alphabetical order
   - Example: prefix "app" -> "apple", "application", "apply"

6. Spell Check
   void spellCheck(struct DictNode *root, char text[]);
   - Read a sentence, split into words
   - Check each word against the dictionary
   - Report misspelled words (not found in dictionary)

7. Word Count
   int countWords(struct DictNode *root);
   - Return total number of words in dictionary

8. Load Dictionary from File
   struct DictNode* loadFromFile(struct DictNode *root, char filename[]);
   - File format: word|meaning (one per line)
   - Build BST from file

9. Save Dictionary to File
   void saveToFile(struct DictNode *root, char filename[]);
   - Save all words to file in alphabetical order

10. Performance Analysis
    - Count tree height after loading from file
    - Compare loading words in sorted order vs random order
    - Display the difference in tree height

================================================================================
MENU INTERFACE
================================================================================

   === Dictionary & Spell Checker ===
   1. Insert word
   2. Search word
   3. Delete word
   4. Display all words
   5. Auto-complete (prefix search)
   6. Spell check a sentence
   7. Word count
   8. Load dictionary from file
   9. Save dictionary to file
   10. Show tree height
   0. Exit

================================================================================
TEST SCENARIOS
================================================================================

a) Insert these words:
   program : a set of instructions for a computer
   algorithm : a step-by-step procedure for solving a problem
   data : facts and statistics collected for analysis
   binary : relating to a system of two
   tree : a hierarchical data structure
   stack : a LIFO data structure
   queue : a FIFO data structure
   array : a collection of elements stored at contiguous locations
   pointer : a variable that stores the address of another variable
   function : a block of code that performs a specific task

b) Display all -> verify alphabetical order
c) Search "algorithm" -> should find and display meaning
d) Auto-complete "a" -> algorithm, array
e) Auto-complete "st" -> stack
f) Spell check "the algorithm uses a binary tree and a stak"
   -> "stak" not found (misspelled)

g) Save to file, reload, verify all words present
h) Compare height when loading sorted vs random order

================================================================================
SAMPLE DICTIONARY FILE (dictionary.txt)
================================================================================

Create a file with at least 30 words related to programming/DSA.
The file should be provided with your submission.

Format:
   algorithm|a step-by-step procedure for solving a problem
   array|a collection of elements stored at contiguous locations
   binary|relating to a system of two
   ...

================================================================================
HANDWRITTEN DESIGN DOCUMENT (Required)
================================================================================

Submit on paper:
1. Draw the BST after inserting the 10 test words above
2. Trace the auto-complete function for prefix "al"
3. Explain how deletion works when removing "data" (node with two children)
4. Draw the BST when words are inserted alphabetically - what shape?
5. How would an AVL tree solve the problem from question 4?

================================================================================
GRADING RUBRIC
================================================================================

| Component                    | Marks |
|------------------------------|-------|
| BST structure & insert       |   10  |
| Search & delete              |   15  |
| Display (alphabetical)       |    5  |
| Auto-complete (prefix)       |   20  |
| Spell checker                |   15  |
| File I/O (load/save)         |   10  |
| Performance analysis         |   10  |
| Handwritten design document  |   15  |
| Total                        |  100  |

Viva Demonstration: Required (multiplier: 0 or 1)

================================================================================
VIVA QUESTIONS:
================================================================================
1. What is the worst-case time complexity of search in your dictionary?
2. How does your auto-complete work? Walk through the algorithm.
3. What happens to your BST if words are inserted in alphabetical order?
4. Add a "suggest similar words" feature that finds words within 1 edit distance (live).
5. How would a balanced BST (AVL/Red-Black) improve performance?
6. What is the space complexity of your dictionary?

================================================================================