Trie data structure in java

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

  • 22 January

    FizzBuzz program in Python

    In this post, we will see how to program FizzBuzz in Python. As per wikipedia, Fizz buzz is a group word game for children to teach them about division. Here are the rules of the game: First player starts the game by saying number 1. Next player says next number but fun part is If […]

  • Format double to 2 decimal places in java
    22 January

    7 ways to format double to 2 decimal places in java

    Learn about how to format double to 2 decimal places in java

  • Escape double quotes in String in Java
    19 January

    How to escape double quotes in String in java

    In this post, we will see how to escape double quotes in String in java. There are scenarios where you need to escape double quotes already present in the String. This generally happens while dealing with JSON file format or reading file data. Escape double quotes in java Double quotes characters can be escaped with […]

  • Convert Date to LocalDate in java
    12 January

    Java Date to LocalDate

    In this post, we will see how to convert Date to LocalDate in java. Sometimes, we may need to convert Date to new Java 8 APIs and vice versa. There are multiple ways to convert Date to LocalDate in java. Read also: Convert LocalDate to Date in java Using toInstant() method of Date class You […]

  • Convert LocalDate to Date in java
    11 January

    Java LocalDate to Date

    In this post, we will see how to convert LocalDate to Date. Java 8 has introduced a lot of new APIs for Date and time. There can be many ways to convert Java LocalDateTime to date. Using Instant object You can convert LocalDate to Date using Instant object which we can from Zone. Here is […]

  • 04 January

    How to change java version in intellij

    Learn about how to change java version in intellij.

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.