A Common-Sense Guide to Data Structures and Algorithms in Python, Volume 1

Trie Insertion

Inserting a new word into a trie is similar to searching for an existing word. We first search to see if the word already exists in the trie. If it doesn’t, we insert the new word.

Here’s how the algorithm goes:

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

2. We iterate over each character of our search string. Here, our search string represents the new word we’re inserting. We call it a search string since we’re also searching whether the string already exists in the trie.

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

4. If it does, we update the current_node to become that child node, ...