Learn

Let’s define the TrieNode class we will use to implement a trie.

To represent subsequent characters in a string, a TrieNode object contains a dictionary that maps a character to an instance of TrieNode. This works somewhat like a linked list in which you have a node that contains information and a pointer to another node.

We represent the TrieNode as the following clas:

class TrieNode: def __init__(self): self.nodes = {}

The self.nodes field is a dictionary that contains the mapping of each character and its subsequent node mapping.

TrieNode also contains a function used to append a character:

class TrieNode: def __init__(self): self.nodes = {} def add_char(c: chr) -> TrieNode: if c not in self.nodes: self.nodes[c] = TrieNode() return self.nodes[c]

We call this method from the Trie class. It returns a TrieNode because a loop in the add_word() method will be responsible for iterating through the nodes starting at the root and placing the characters where they need to be. There are two possible scenarios:

  • The current TrieNode already contains an entry for character c because it has been entered earlier as the prefix to another word. In this case, add_char() retrieves the TrieNode mapped to c and returns it.
  • The current prefix has not been entered. Therefore, TrieNode does not contain a mapping for the character c. In this case, add_char() creates a mapping and returns it. add_word() will continue to load the word into the trie.

We can augment the TrieNode class to hold other relevant information about a word.

Instructions

1.

Modify the TrieNode class to contain a field that represents whether or not a current character is the end of a word. Call this field end_of_word, and add it to the __init__() constructor.

Set end_of_word to False.

2.

Modify the TrieNode class to contain a field that will represent the number of times that this node has appeared in a prefix. Call this field freq, and add it to the __init__() constructor.

Set freq to 0.

Sign up to start coding

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?