Goal

Write a trie for storing word frequency in Python$3.$

Background

Tries can be used to store the frequency of words used in a body of text. A common use $($before AI$)$ is to use them

to suggest the next word given a partial word. For example, if you type 'ave' into a system using word frequency to

predict the full word, the system might suggest 'average' if this word occurs most often.

General Instructions

I have provided a sample tester file homework$2\_$test.py$.$ Use this to test your work. NOTE: we will use a

different tester when grading. This means, do not hardcode your work to include the words in the tester. This

file is there to give you an idea a$)$ how to test and b$)$ what we will test. You are free to create your own testers

beyond this one.

Your homework submission must be called

homework$2.$py$.$ Please put a comment at the top with your full

name. If your submission does not have this exact filename you will lose points.

Submit only your

homework$2.$py file. We do not need sample output or your personal test code.

homework$2.$py should only contain the two classes mentioned below.

You are free to include additional helper functions in your classes if you see fit. However, they should not be

the entry point for any of the below operations. Treat the following list of functions as each classes' interface.

NOTE: I have not given you the interface for the TrieNode class. How you implement this is up to you. Use of

the Trie class should not depend on knowing anything about the TrieNode. It should be invisible.

TrieNode Class Requirements

Again, I am not providing an interface for this class; however, it should store the following data.

word: The word or partial word corresponding to this node.

word count: If this word is a real word $($i$.$e$.,$ not a prefix or partial word$),$ how many have been added to the

trie.

$26$ child links: Links to the child nodes of words that have this word as their prefix.

You may add other data as you see fit.

The node class must make a distinction between nodes storing information about real words versus partial words.

For example, let's say I add the word 'happy' to the tree. Assuming the trie is empty, it would generate five nodes:

$\text{'}$h$\text{'}$

$\text{'}$ha$\text{'}$

'hap'

'happ'

'happy'

Only the leaf node $(\text{'}$happy$\text{'})$ would count as a real word. The other four nodes should register as partial words and

not be included in word counts.

Trie Class Requirements

class Trie:

The class must be called Trie.