Insertion in a Trie

Word Insertion #

The insertion process is fairly simple. For each character in the key, we check if it exists at the position we desire. If the character is not present, then we insert the corresponding trie node at the correct index in children. While inserting the last node, we also set the value of isEndWord to True.

There are three primary cases we need to consider during insertion. Let’s discuss them now.

Case 1: No Common Prefix #

In this situation, we want to insert a word whose characters are not common with any other node path.

The illustration below shows the insertion of any in a trie which consists of only the.

We need to create nodes for all the characters of the word any as there is no common subsequence between any and the.