- Trie is a multi-way search tree where each node represents each character and all the children of the same will be having a same prefix.
- Rather than storing the character each node will be storing the prefix.
- Structure of the Node :
String prefix;
Node[26] children;
Each node will hold an array of 26 nodes where each node represents the each letter. If some letter is not present then that will be empty. It is an overhead of trie because it used extra memory which is not using.
- Now we have to think about how to organize or store the array of nodes.
Two possibilities are 1) Store as array
2) Store as linked list
If you store as array we can access it in a indexed way,but we have to waste much memory.
if you store as linked list then access time of the search string will increase( search in linked list of 26 nodes is O(26) and we need to travel m levels where m is the length of search string, that sums to O(m*26)) but memory usage will be optimal.
But if we use HashMap then you can get the time complexity O(1) and memory also will be optimal O(n).
