A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Trie Insertion

Inserting a new word into a trie is similar to searching for an existing word.

Here’s how the algorithm goes:

1. We establish a variable called currentNode. At the beginning of our algorithm, this points to the root node.

2. We iterate over each character of our search string.

3. As we point to each character of our search string, we look to see if the currentNode has a child with that character as a key.

4. If it does, we update the currentNode to become that child node and we go back to Step 2, moving on to the next character of our search string.

5. If the currentNode does not have a child node that matches the current character, we create such a child node and update the currentNode to be this new node. We then go back to Step 2, moving ...