Learn

In this exercise, we will describe the algorithm that adds a word to a trie. We will then implement this algorithm in the add_string() function of the Trie class. We will be implementing this algorithm iteratively.

Let’s go over the algorithm to add a string to a trie step-by-step:

  • Begin by creating a pointer that initially points to the root node of the Trie.
  • Iterate through the characters of the string parameter using a loop.
  • Take the first character and call the root node’s add_char() method passing in the character as a parameter.
  • The add_char() method processes the character according to its logic.
  • The add_char() method then returns the node associated with the current character.
  • The pointer will now point to the node returned from add_char().
  • Before the loop continues, the returned node associated with the character has a freq variable that is keeping track of the number of prefixes up to this character. freq is now incremented.
  • The loop repeats this process for the remaining characters.
  • The very last node, representing the last character in the string, will have its end_of_key set to True to indicate that this is the end of a string.

To review this, let’s take a look at an example. We wish to add the word “CODE” to the trie:

  1. We call add_word(CODE).
  2. Inside add_word(), we initialize a pointer to the root of the trie.
  3. A loop is created that will iterate through “CODE”.
  4. We will call root.add_char('C').
  5. The root.add_char() function will create an entry in the root node’s nodes dictionary if one does not already exist.
  6. root.add_char() will return the node that is associated with the character ‘C’.
  7. We set the pointer to this node.
  8. We increment the freq variable by one to represent that this node (this character) is part of freq amount of prefixes.
  9. The loop proceeds on to the next letter ‘O’ and repeats steps 2-9 for the remaining characters.
  10. In the end, the node representing the character ‘E’ will have its end_of_key variable set to True.

Let’s implement this algorithm in the add_string() method!

Instructions

1.

Inside the add_string() method, initialize a pointer to the root node and call it nxt.

CLick the hint if you get stuck.

2.

Loop through the characters of string (the string parameter that is passed into add_string()) and add them to the trie.

3.

The freq variable in this node represents the number of words that contain the prefix up to this character. Since a prefix was just added, modify the freq variable to represent this addition.

As an example, consider a trie containing the following words:

  • ADD
  • ADDITION
  • ADDENDUM

The freq variable in the nodes ‘A’, ‘D’, and ‘D’ will be set to 3 because there are three words that contain the prefix ADD.

A word counts as its own prefix.

4.

After the loop has completed entering the string into the trie, set the last node’s (character’s) end_of_key variable to True which represents that this character is the end of a word.

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?