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.