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

  • Count files in folder in PowerShell
    01 January

    PowerShell – Count Files in Folders

    Table of ContentsCount Files in Folders in PowerShellCount Files in multiple Folders in PowerShellCount Files in Folders and Subfolders in PowerShellCount only folders inside folder in PowerShellCount Files by Extension in Folder in PowerShell Count Files in Folders in PowerShell We can use the Measure-Object cmdlet in different ways to meet our project requirements. However, […]

  • Check if Object contains property in PowerShell
    31 December

    Check if Object has Property in PowerShell

    Table of ContentsUsing the -match ParameterUsing -contains ParameterUsing if-else BlockUsing .Match() Function with if-else BlockUsing Get-Member Cmdlet Using the -match Parameter Use the -match parameter to check if an object has a property in PowerShell. [crayon-63b3e043535f6153139762/] [crayon-63b3e043535fb230509528/] Here, we used the -match parameter to check if the given object, which is $result in our case, […]

  • Create Empty File in PowerShell
    28 December

    Create Empty File in PowerShell

    Table of ContentsUsing New-Item CmdletUse the ni AliasUsing Out-File CmdletUsing the fsutil file CommandUsing Text EditorUsing echo CommandUsing for Loop Using New-Item Cmdlet Use the New-Item cmdlet to create an empty .txt file in PowerShell. [crayon-63b3e04353b8d464877747/] [crayon-63b3e04353b91651361804/] We used the New-Item cmdlet with -Path, -Name, and -ItemType parameters to create an empty .txt file using […]

  • 27 December

    Run PowerShell as Another User

    Table of ContentsUsing the runas CommandOpen the PowerShell as an AdministratorRun the runas commandUsing the Start-Process cmdlet with the Credential ParameterUI-Based SolutionScript-Based Solution Using the runas Command The runas command in PowerShell launches programs using credentials different from the current user. It provides users with limited privileges to execute commands or access resources available only […]

  • 27 December

    Create Array of All NaN Values in Python

    Table of ContentsUsing numpy.empty() FunctionUsing numpy.full() FunctionUsing numpy.tile() FunctionUsing numpy.repeat() FunctionUsing Multiplication of numpy.ones() with nan Using numpy.empty() Function To create an array of all NaN values in Python: Use numpy.empty() to get an array of the given shape. Assign numpy.nan to every array element using the assignment operator (=). [crayon-63b3e043545bb866995633/] [crayon-63b3e043545bf701044993/] We used numpy.empty() […]

  • 27 December

    Call Function from Another Function in Python

    Table of ContentsCall a Function in PythonCall Function from Another Function in PythonCall a Function from Another Function within the Same/Different Classes Call a Function in Python To call a function in Python: Write a test() function, which prints a message. Call the function defined in the previous step. [crayon-63b3e04354758978620439/] [crayon-63b3e0435475b889234642/] To call a function, […]

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.