Insertion in a Trie

Inserting a word in Trie

Insertion is simple for individual characters in the trie. If the character is already present, we follow the path; if that character is not present, then we insert the corresponding nodes. While inserting the last node, we must also set the value of isEndWord() to true.

Case 1: What if the word has no common subsequence? i.e. No Common Prefix

For example, if we want to insert a new word into the trie below, e.g. “any”, then we need to insert all of the characters for the word “any”; currently, “the” is the only word in the trie, and there are no common character subsequences between “any” and “the”.

Case 2: If the word has a common subsequence? i.e. Common Prefix Found

For example, if we want to insert the word “there” into the trie below-- which already consists of the word “ their”–then the path to “ the” already exists. After that, we need to insert two ...