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

  • Check if String contains Substring in PHP
    25 October

    How to check if String contains substring in PHP

    Table of ContentsIntroductionHow to check if a string contains substring in PHP?1) strpos() function:2) strstr() function:3) stristr() function:4) preg_match() function: Introduction A string is a sequence of characters used as a literal constant or variable. The specific part of a string is known as a substring. In this article, we will see different ways to […]

  • 25 October

    Increment operator in python

    Table of ContentsPython’s distinct way of using the increment operatorWays to increment a variable in PythonUsing the augmented assignment operatorUsing the step parameter in the range() functionThe role of immutability in Python The increment process is among the basic and the essentials of any programming language. We use it in problem-solving and when there is […]

  • Initialize list with zeros in Python
    25 October

    Four Ways To Initialize List With Zeros In Python

    Table of ContentsWhy Initialize List with Zeros in Python?How Can We Initialize List With Zeros In Python?Initialize List With Zeros Using * Operator In PythonInitialize List With Zeros Using  itertools.repeat() FunctionInitialize List With Zeros Using  Generator Comprehension In PythonInitialize List With Zeros Using  List Comprehension In PythonConclusion Lists in Python are one of the most […]

  • How to print an array in PHP
    19 October

    How to print an array in PHP

    Table of ContentsIntroductionHow to print an array in PHP?1) print_r() function:2) var_dump() function:3) json_encode() function:4) foreach() loop: Introduction An array is one kind of data structure, which can store multiple items of related data types. The printing of an array is one of the fundamental functions of PHP. How to print an array in PHP? […]

  • Multiple classes in one file in Java
    18 October

    Multiple classes in one file in Java

    Table of ContentsIntroductionMethods to Implement Multiple Classes In One Java Program1) Nested classes2) Multiple non-static nested classes In this post, we will see how to have multiple classes in one file in java. Introduction You need to have any number of classes in a single Java file, but there is a restriction that you can […]

  • How to initialize empty array in PHP
    18 October

    Declare empty array in php

    Table of ContentsUsing square brackets to declare empty array in PHPUsing array() to declare empty array in PHP An array is a data structure where you can store the same or different types of data in a single variable. In PHP, you can declare empty array using square brackets ([]) or using array() function. Using […]

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.