Trie Data Structure

Today I want to discuss about new data structure called Trie. Its pronounced as Tree or Try.

I came to know about this data structure because of the following requirement.

Want to find If Arraylist contains substring.
Example: Arraylist has {“hello world”, “Mandarine Garden”, “Panda Express”, “Olive Garden”}
Now I want to check if the word “Olive” is in the arraylist atleast substring.

One way of doing it is iterating through the array list , comparing each string with substring method and checking.

This way we can do if the arraylist size is small, but if you have size of 10000 it may not be desirable.
So I figured out that trie data structure is the solution. Where it supports a insert, delete, find prefix etc.

You can find the code samples in my Github (Route Finder) Project.