Trie (aka digital tree or radix tree) is an ordered tree data structure used for efficient information retrieval from an index comprising of set of strings.
Nodes usually store character in the indexed string. Node would possibly have multiple branches and hence representing multiple strings formed out of the character sequence.
Time complexity is O(m) where m is the length of the key.
Memory requirement is one downside of Trie and hence suitable of small dataset.
Good example of trie in real life is the data structure behind the phone book in mobile phones. As and when a character is keyed-in, it shows the shortlisted contact names.
