A trie is a kind of search tree – an efficicent information re
Trieval data structure. Using Trie, search complexities can be brought to optimal limit.
If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using Trie, we can search the key in O(M) time. However the penalty is on Trie storage requirements.
Illustration by WikiPedia