In this exercise, we will search for a string in a trie. A string is loaded into a trie for one of two reasons:

• The trie represents a dictionary of words.
• The string contains some relevant information.

The function search_string() in our Trie class will search the trie for the string and return whether it is there or not. We can modify this function to return relevant data associated with the string, but for our purposes, we will only determine whether the string is in the trie or not.

Here are the steps of the algorithm to search for a string:

• Initialize a pointer to the root node in the trie.
• Create a loop that will loop through all the characters of the string passed into search_string().
• Access the current node’s nodes dictionary and attempt to retrieve the node associated with the current character.
  • If the node exists, set the pointer to this node.
  • If the node does not exist, that means this string is not there; therefore, the loop should terminate immediately, and search_string() should return False.
• Assuming the word exists, the loop will repeat this process for all remaining characters.
• At the end of the loop, the pointer points to the node associated with the last character in the string; therefore, the function should return the value associated with end_of_key.

Please note that we return the value of end_of_key and not True because we want to know if this string is a full entry. A string may exist in the trie only because it is the prefix to a longer string. In that case, we should return False because the string has not been entered as its own word.

Let’s take a look at an example. We have a trie that contains the word CODECADEMY.

We will search this trie for the word CODE (this word has not been entered into the trie):

1. Initialize a pointer to the root node.
2. A loop will loop through all characters of CODE.
3. We will access the root node’s nodes dictionary to retrieve the node associated with the letter ‘C’.
4. We will set the pointer to that node.
5. Repeat steps 2 through 4 for the remaining characters.
6. This loop will not terminate early because the string CODE exists in the trie as a prefix of CODECADEMY.
7. After the loop terminates, the pointer will point to the node associated with the letter ‘E’.
8. Return the value of the end_of_key variable of the node associated with the letter ‘E’. This will be False because CODE does not exist in the trie as its own word.

If you search for the word CODECADEMY, search_string() will return True.

If you search for the word COCOA, search_string() will terminate early and return False because there is no node associated with the second ‘C’.

If there is relevant information associated with the word, it will likely be stored as a field in one of the TrieNodes. If you want that, have search_string() return it!