Trie data structure in java

If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.

In this post, we will see about trie data structure in java.

What is Trie :

Trie is data structure which stores data in such a way that it can be retrieved faster and improve the performance.

Some real time examples:

Trie can be used to implement :
Dictionary
Searching contact in mobile phone book. 

Trie data structure:

You can insert words in trie and its children linked list will represent its child nodes and isEnd defines if it is end for the word.
Example:
Lets say, you want to insert do, deal , dear , he , hen , heat etc.
Your trie structure will look like as below:

TrieNode will have following variables and method.

Each TrieNode have access to its children if present at all. It contains current data, count , isEnd and childList. isEnd is a boolean variable which represents if current Trie node is end of word or not.childList will have list of children for that TrieNode.

Algorithm for inserting word in Trie structure:

  • If word already exists, return it.
  • Make current node as root trie node
  • Iterate over each character(lets say c) of word.
  • get child trie nodes for current node
    • If child node exists and is equal to character c then make it current node and increment the count.
    • If child node does not exist, then create a new trie node with character c and add it to current node childList and change current node to newly created trie node.
  • When you reach at end of the word, make isEnd = true.
Java Code:

Algorithm for searching a word in Trie data structure:

  • For each character of word , see if child node exists for it.
    • If child node does not exists, return false
  • If character exists, repeat above step
  • When you reach at end of the String and current.isEnd is true then return true else return false.

Java code to implement Trie data structure

When you run above program, you will get below output

Related Posts

  • Kimcartoon alternatives
    21 July

    KimCartoon alternatives -13 Best Websites Like KimCartoon in 2021

    Table of ContentsBest KimCartoon alternatives in 2021CartoonsOnToonovaKissAnimeToonGetWatch Cartoons OnlineCartoonCrazyAnimedaoAnimeToonCartoon ExtraEyeonanimeNyaaMasteraniToonJetFrequently Asked Questions Is KimCartoon safe in 2021?Is KimCartoon legal in 2021?Is there any working proxy of KimCartoon in 2021?Wrapping Up Are you worried about KimCartoon getting shut recently? Well, we’ve you covered. KimCartoon has been one of the best platforms for seamlessly streaming cartoons in HD. […]

  • Trim String in C++
    19 July

    Trim String in C++

    Table of ContentsUsing Boost string algorithms to trim string in C++Using find_first_not_of() and find_last_not_of()` to trim strings in C++Using find_if() to trim the string in C++Using stringstream to trim the strings in C++Using a customized function to trim the strings in C++Conclusion When we take an input from an user, strings can have unwanted whitespaces […]

  • JSON parser in C++
    19 July

    JSON Parser in C++

    Table of ContentsSimple JSON Parser in C++ using JsonCpp libraryConclusion In this post, we will see about JSON parser in C++. There is no native support for JSON in C++. We can use a number of libraries that provide support for JSON in C++. We will use JsonCpp to parse JSON files in C++ which […]

  • Enum to String in C++
    19 July

    Convert enum to string in C++

    Table of ContentsUsing stringify macro method to convert enum to String in C++Using const char* Array to convert enum to String in C++Using a custom-defined function to convert enum to String in C++Conclusion There are a variety of methods to convert enum to String in C++. In this article, we will discuss some of the […]

  • sites like 123movies
    18 July

    13 Best Sites Like 123movies Working in 2021

    Table of ContentsBest sites like 123movies in 2021F MoviesJust WatchTV MusePopcornFlixVid StrumSoap2dayWatch SeriesXfinityWatch EpisodeTubi TVRainer LandCravePrime WireBest Working Proxy of 123movies Working in 2021Frequently Asked Questions What is 123movies? Why do you need sites like 123movies? Are there any Free sites like 123movies? Wrapping Up For quite some time now, 123movies has been the one-stop destination for watching movies […]

  • open source PDF editor
    18 July

    The Best Free Open Source PDF Editor for Windows and Mac in 2021

    Table of ContentsBest Open Source PDF Editor in 2021InkScapeApache OpenOffice DrawPDFSamLibreOffice Draw PDF EditorPDFeditOkularEaseUS PDF Editor (Free)SkimPDF Architect (Free)Frequently Asked QuestionsWhat do you mean by an open source PDF editor? Is there an open source PDF editor?Can I edit a PDF for free?Which are the best free open source PDF editors?Wrapping Up Are you looking for […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.