🙏

জয়  শ্রী  রাম

🕉

---

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:



Login to Access Content

Applications of Trie:

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

Instructor: