Implement Trie Data Structure in Java

Trie is a tree-based data structure used for efficient retrieval of a key in a huge set of strings. In this post, we will implement Trie data structure in Java.


 

 
In the previous post, we have discussed about Trie data structure in detail and also covered its implementation in C. In this post, Java implementation of Trie data structure is discussed which is way more cleaner than the C implementation.

 
Below is Java implementation of Trie data structure which supports insertion and search operations. The implementation currently supports only lowercase English characters (a – z) but the solution can be easily extended to support any set of characters.

 

Download   Run Code

 
The space complexity of a Trie data structure is O(N*M*C) where N is the number of strings and M is the highest length of the string and C is the size of the alphabet.

The storage problem can be alleviated if we only allocate memory for alphabets in use and don’t waste space storing null pointers. Below is memory efficient implementation of Trie Data Structure in Java which uses HashMap to store children of a node.

 

Download   Run Code

 
Also see: C++ Implementation of Trie Data Structure (Insert, Search and Delete)

 
Thanks for reading.

Please use our Java Shell to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
yndi
Guest

Both provided implementations are incorrect. The removal logic of the array-based one is broken, an ArrayList is treated as it were a HashMap. Despite that, deletions seem to work fine because each node aways has CHAR_SIZE children and those conditions never activate. However, by keeping zombie nodes, the memory layout becomes inefficient (inserting and removing “abc” will keep all three nodes in the trie). The hash table-based implementation just corrupts the trie, imagine inserting “ab” and “ac” and deleting “ac”, in the current implementation, this will also delete “ab”.