Everyone has seen or even used a dictionary - may be this statement is more true of people from my generation than younger generations. In any case, a phonebook app in a smartphone also lists contact names in alphabetical order. Aakash would precede Amar which would precede Amit which preceeds Aqsa and so on. The common prefix between Amar and Amit is ‘Am’ - which tells us we could a tree data-structure, storing ‘Am’ in a node which has two children storing ‘i’, ‘a’ and so on. This also makes search easy and it follows the same technique we use to search for a word in a dictionary.

There are several other applications where identifying and storing prefixes of strings efficiently can be very useful. Think about auto-completions in a texting app or Google search or how a router could do address matching efficiently.

This data structure must be something very popular as it seems to have several everyday and important applications. And it is the “Trie”. Whenever we have a large number of strings (like protein sequences or words in a language or all possible strings one could type in a Google search box) that share some common prefix, we need to use think about efficiently matching shared prefixes. Trie is very simple and straight-forward to implement as we will see in a future post.