1. TrieNode class #

Created Saturday 07 March 2020

Advantages of tries over hashMaps:

• Both hashMaps and tries have nearly the same time complexity: Trie is somewhat better though.
• We have to store each letter on it’s own in a hashMap Space = sum of number of letters in each word. While in trie, words are decreased significantly. i.e all words having some common initial thing. This is very difficult for hashMaps, as hash works on the whole string and not on parts. Even if we somehow link the parts adding a word in between two words would be very difficult. We’d have to break the string.

Attributes:

• char data
• children list - use simple array of trinode addresses. Of size 26.(assuming lowercase English) Does this waste space - no it does not, as we can access the letters in 1 step. If we used a vector, we’d have to search the whole array, 26 steps to be precise in the worst case.
• bool isTerminal, true if yes, false if no.

Operations:

• search(string key)

If travel is possible for the whole length **and **that the last letter is a terminal, return true. Else false.

• add(string word)

Traverse the initial part of the word, as much as possible in the trie. Three cases are possible:

1. The word exists completely and the last letter is a terminal, do nothing.
2. The word exists completely but the last letter is not a terminal, set the node’s isTerminal to true.
3. The word exists partially(or not at all), create nodes for all the letters. For the last letter node, set isTerminal to true.

• remove(string word)

Two cases are possible:

1. The word does not exist. Do nothing.
2. The word exists. Delete the last node if it is a non terminal and a non-parent. Keep doing this for the parents, if they also are a non-terminal and a non-parent of children.

Doubt: How to delete parents? Answer:

1. Make an array of length the same as the word_length which needs to be deleted.
2. Traverse the word in the trie and note the parents.
3. Once done, iterate through the list right to left. Keep deleting if the node is a non-parent and a non-terminal. Once this condition becomes false. Stop.