• 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.
  • If you are a student, email to admin@thealgorists.com to get special student discount.




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.




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




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