Insertion in a Trie
This lesson defines all the cases needed for inserting a word into a trie, along with the C# implementation.
We'll cover the following
Word insertion
The insertion process is fairly simple. For each character in the key, check if it exists at the position desired. If the character is not present, then insert the corresponding trie node at the correct index in children
. While inserting the last node, set the value of isEndWord
to true
.
There are three primary cases you need to consider during insertion. Let’s discuss them now.
Case 1: No common prefix
In this situation, you 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
.
You need to create nodes for all the characters of the word any
as there is not a common prefix between any
and the
.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.