Trie data structure

Today I will write about a magical data structure namely Trie.

When we talk of storing and retriving some information about a bunch of strings, Trie comes to our rescue.

Basically Trie consists of a root TrieNode and 26 children. Each child in turn represents a TrieNode with another set of 26 children and so on.

Suppose we want to store a word "sid" in our trie data structure, so initially we place our pointer at the root and move from the root to the - ('s' - 'a')th indexed child of the root and place the 's' over there, then we move our pointer to the created 's' node and add another node at ('i' - 'a')th child of the 's' node and similarly we do it for the last 'd' character as well after moving our pointer to the created 'i' node.

Explaining the above through the below code -

The additional boolean namely isWordEnd to denote if a string ends at this node.

Now it is time to see the code to insert a word into the trie -

After inserting the words into the Trie, next purpose is to search for the word in the Trie, algorithm that is popularly used in implementing dictionary, word suggestions etc.

Let us see the code for it -

Finally combining everything, let us see how do we leverage the above code for our purpose -

The Time Complexity for both Inserting and Searching is O(n), where n is the length of the string being inserted or being searched for.

The Space Complexity for Inserting a word is O(n), where n is the length of the string being inserted. Whereas for searching for a word in a Trie, we do not require any auxilliary space(O(1)).

Through this article I wanted to explain the basics of the Trie data structure and its implementation. We can build on it, I would encourage the readers to implement more things on top of these and solve bigger problems using this magical data structure. Happy coding.