• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.




In computer science, a trie, also called digital tree or prefix tree, is an n-ary tree used for locating specific keys from within a set. Its nodes store the letters of an alphabet and point to multiple child nodes. In order to access a key (to recover its value, change it, or remove it), the trie is traversed depth-first. The two most important uses of Trie are:

  • Given a dictionary (i.e, list or group of words) and given a prefix, search if there is one or more words in the dictionary starting with the given prefix.
    If the length of the prefix is M, the time complexity of this operation would be O(M).

  • Given a dictionary (i.e, list or group of words) and given a word, search if the dictionary contains the word.
    If the length of the word is M, the time complexity of this operation would be O(M).

Below is the process to build a trie containing the words “tree”, “trie”, “algo”, “string” and “struct”.



Code Implementation:


Functionalities :

addWord -> adds a given word to the dictionary
removeWord -> removes a word from a dictionary
find -> finds number of words present in the dictionary with a given prefix
numWords -> number of words present in the dictionary
printWordsWithPrefix -> prints words with a given prefix
isWord -> determine if a given string is present in a dictionary
isPrefix -> determines if a given string is a prefix to any word in the dictionary. Point to remember is that a word is also a prefix to itself.

I have put all the implementation details and the detailed algorithmic discussion in the inline comments in the code below:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





Applications of Trie:

1. Auto Completion
2. Spell Checker
3. Longest Prefix Matching (Algorithms used by routers in Internet Protocol or IP)

The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave