Do not use any helper functions or new functions and use tester.py to test code

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:Implement 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.

Use Lab-Tester.py to test your code

Example command line

$python Lab5-Tester.py Lab-Template.py

Lab-Template.py

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 BIC should have length 2 passimport random import string import re #Module Imports import string import sys from importlib import import_module wordlist = def GenerateWord(size) : chars=string. ascii_letters+"!" word=" " for i in range(0, random. randint (size/2, size)): word += random. choice (chars) return word def diff (lil, li2) : return (list(list(set(lil)-set(li2)) + list(set(1i2)-set(lil))) ) def Test(lib, seed=0, size=10, rounds=10, verbose=False, wordlist=None): if wordlist is None: wordlist = if not lib: print( "You need to include a testable library") return False if not wordlist: f = open ("american-english-no-accents. txt", "r") readwords = f. readlines() for word in readwords: wordlist . append (word. rstrip( ) ) random. seed (a=seed) trie = lib.MyTrie() for word in wordlist: trie. insert (word) if len(wordlist) != len(trie): if verbose: print ( "Trie size mismatch!") return False if verbose: print ( "Insertion test complete") yield Truefor j in range(0, rounds) : expected = True if random. randint (0, 2) == 0: c = GenerateWord(6) else: c = wordlist [random . randint(0, len(wordlist) ) ] expected = c in wordlist res = trie. exists(c) if res != expected: if verbose: print ( "Word " + " was " + ( "found" if res else "not found") + " and was expected to " + ("" if expected else "not") + " be.") return False if verbose: print("Trie item test complete") yield True try : mlist = trie. autoComplete("") except: if verbose: print ("Error: Autocomplete method not callable") return False if not (mlist == wordlist) : if verbose: print("Error: Autocomplete missing items for empty list") missing = diff (mlist, wordlist) print (missing) return False if verbose: print("Complete retrieval test complete") yield True try : emptyList = trie . autoComplete("fasdfasdfasdfasfawef" ) except: if verbose: print("Error: Autocomplete does not respond to unmatched prefix") return False if len(emptyList) != 0: if verbose: print("Error: Autocomplete returning items for unmatchable prefix") return Falseif verbose: print( "Unmatchable prefix test complete") yield True for j in range (0, rounds) : W= III while len(w)