Trie Data Structure
Fundamentals and Code Implementation
Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io
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).
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)
Senior SDE | Chief Architect
Microsoft | University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.