Given: You are given a Python Class template, and a list of words in the

file 'american-english-no-accents.txt'. In the template

Task:create a recursive trie data structure. Each node should store either

a character or a word. Then, implement the autocomplete method. This

method should recursively explore the trie and return a list of all

words in the trie that match that prefix. The list must be in

alphabetical order.

Example:

Given the words 'dad', 'daddy', 'daddio', 'danny', 'mum',

and 'mummy', the trie should look like this:

|d|m|

/\

|a||u|

/\

|d | n||m|

/\\

|d | #|danny|m | #|

/\/\

|i | y|dadmummymum

/\

daddiodaddy

When the prefix 'da' is autocompleted, the list returned should be:

['dad', 'daddio', 'daddy', 'danny']. When the prefix '' is given,

every word in the trie should be returned, in alphabetical order.

When the prefix 'uncl' is given, an empty list should be returned.

Notes: Ensure that duplicate words do not get added to the trie twice.

Both lower and upper case letters will be used. Consider them as

seperate characters, upper case letters coming before lower case.

The file 'american-english-no-accents.txt' is used by the tester

but you can create a own test dictionary and tester program.

Python Class Template:

def getName():

return "Last name, first name"

class MyTrie:

def __init__(self):

# Initialize the trie node as needed

self.children = {}

self.children_count = 0

self.word = None

self.autocomplete_list = []

def insert(self, word):

# Insert a word into this trie node

pass

def exists(self, word, position=0):

# Return true if the passed word exists in this trie node

# A terminal node will return true if the word passed is ""

pass

def isTerminal(self):

# Return true if this node is the terminal point of a word

pass

def autoComplete(self, prefix, position=0):

# Return every word that extends this prefix in alphabetical order

pass

def __len__(self):

# Return the number of words that either terminate at this node or descend from this node

# A terminal leaf should have length 1, the node A with terminal child leaves B|C should have length 2

pass