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

Output:

Inserting “techie”
Inserting “tech”
Searching “tech” : true
Searching “techie” : true
Searching “techiedelight” : false
Inserting “techiedelight”
Searching “techiedelight” : true

 
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

Output:

Inserting “techie”
Inserting “tech”
Searching “tech” : true
Searching “techie” : true
Searching “techiedelight” : false
Inserting “techiedelight”
Searching “techiedelight” : true

 
Exercise: Extend the implementation to support deletion operation.

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

 
Thanks for reading.




Please use ideone or Java Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz