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

Was this post helpful?

Related Posts

  • 24 September

    Display Negative Number in Parentheses in Java

    In this post, we will see how to display negative number in Parentheses in Java. We can use pattern #,##0.00;(#,##0.00) with DecimalFormat‘s format() to display negative number in Parenthesis in Java. [crayon-633025cea0da6904257841/] Output [crayon-633025cea0daf004915211/] If you don’t need decimal places, you can change to pattern to: [crayon-633025cea0db1828335180/] Let’s understand meaning of pattern #,##0.00;(#,##0.00): First part […]

  • 24 September

    Increment for Loop by 2 in Java

    Table of ContentsHow to increment for loop by 2 in JavaHow to increment for loop by n in Java In this post, we will see how to increment for loop by 2 in Java. There are several looping statements available in Java and one of them is for loop in java. There are three parts […]

  • 24 September

    Get List of Month Names in Java

    Table of ContentsUsing DateFormatSymbols’s getMonth() methodUsing DateFormatSymbols’s getShortMonths() method [ For short names]Using DateFormatSymbols’s getMonth() with Locale In this post, we will see how to get list of months name in Java. Using DateFormatSymbols’s getMonth() method We can use DateFormatSymbols's getMonth() to get list of months in Java. It will provide complete month names like […]

  • 24 September

    Escape Percent Sign in printf Method in C++

    In this post, we will see how to escape percent sign in printf Method in C++. Escape percent sign in Printf Method in C++ printf() method uses percent sign(%) as prefix of format specifier. For example: To use number in prinf() method, we use %d, but what if you actually want to use percent sign […]

  • 23 September

    Convert 0 to 1 and 1 to 0 in Python

    Table of ContentsWays to convert 0 to 1 and 1 to 0 in PythonUsing SubtractionUsing XORUsing not operatorUsing lambda expressionUsing addition and remainder operatorConvert 1 to 0 and 0 to 1 in listConvert 1 to 0 and 0 to 1 in numpy arrayUsing where with bitwise xorUsing bitwise operators In this post, we will see […]

  • 23 September

    TypeError: Object of Type Datetime Is Not Json Serializable in Python

    Table of ContentsFix the object of type datetime is not JSON serializable exception in PythonUsing the default parameter in the json.dumps() functionUsing the cls parameter in the json.dumps() functionUsing the str functionConclusion In Python, the datetime library allows us to create objects of the datetime class that can store and process date and time values […]

Leave a Reply

Your email address will not be published.

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.