Table of Contents
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.
When you run above program, you will get below output
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class TrieNode { char data; boolean isEnd; int count; LinkedList<TrieNode> childList; /* Constructor */ public TrieNode(char c) { childList = new LinkedList<TrieNode>(); isEnd = false; data = c; count = 0; } public TrieNode getChild(char c) { if (childList != null) for (TrieNode eachChild : childList) if (eachChild.data == c) return eachChild; return null; } } |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* This function is used to insert a word in trie*/ public void insert(String word) { if (search(word) == true) return; TrieNode current = root; for (char ch : word.toCharArray() ) { TrieNode child = current.getChild(ch); if (child != null) current = child; else { // If child not present, adding it io the list current.childList.add(new TrieNode(ch)); current = current.getChild(ch); } current.count++; } current.isEnd = true; } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
/* This function is used to search a word in trie*/ public boolean search(String word) { TrieNode current = root; for (char ch : word.toCharArray() ) { if (current.getChild(ch) == null) return false; else current = current.getChild(ch); } if (current.isEnd == true) return true; return false; } |
Java code to implement Trie data structure
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
package org.arpit.java2blog; /* * Java Program to Implement Trie */ import java.util.*; class TrieNode { char data; boolean isEnd; int count; LinkedList childList; /* Constructor */ public TrieNode(char c) { childList = new LinkedList(); isEnd = false; data = c; count = 0; } public TrieNode getChild(char c) { if (childList != null) for (TrieNode eachChild : childList) if (eachChild.data == c) return eachChild; return null; } } public class TrieDataStructure { private TrieNode root; /* Constructor */ public TrieDataStructure() { root = new TrieNode(' '); } /* This function is used to insert a word in trie*/ public void insert(String word) { if (search(word) == true) return; TrieNode current = root; for (char ch : word.toCharArray() ) { TrieNode child = current.getChild(ch); if (child != null) current = child; else { // If child not present, adding it io the list current.childList.add(new TrieNode(ch)); current = current.getChild(ch); } current.count++; } current.isEnd = true; } /* This function is used to search a word in trie*/ public boolean search(String word) { TrieNode current = root; for (char ch : word.toCharArray() ) { if (current.getChild(ch) == null) return false; else current = current.getChild(ch); } if (current.isEnd == true) return true; return false; } /* This function is used to remove function from trie*/ public void remove(String word) { if (search(word) == false) { System.out.println(word +" does not present in trien"); return; } TrieNode current = root; for (char ch : word.toCharArray()) { TrieNode child = current.getChild(ch); if (child.count == 1) { current.childList.remove(child); return; } else { child.count--; current = child; } } current.isEnd = false; } public static void printAllWordsInTrie(TrieNode root,String s) { TrieNode current = root; if(root.childList==null || root.childList.size()==0) return; Iterator iter=current.childList.iterator(); while(iter.hasNext()) { TrieNode node= iter.next(); s+=node.data; printAllWordsInTrie(node,s); if(node.isEnd==true) { System.out.print(" "+s); s=s.substring(0,s.length()-1); } else { s=s.substring(0,s.length()-1); } } } public static void main(String[] args) { TrieDataStructure t = new TrieDataStructure(); t.insert("dear"); t.insert("deal"); t.insert("do"); t.insert("he"); t.insert("hen"); t.insert("heat"); System.out.println("hen present in trie : "+t.search("hen")); System.out.println("hear present in trie : "+t.search("hear")); System.out.println("deal present in trie : "+t.search("deal")); System.out.println("========================"); System.out.println("Printing all word present in trie : "); printAllWordsInTrie(t.root,""); } } |
|
1 2 3 4 5 6 7 8 |
hen present in trie : true hear present in trie : false deal present in trie : true ======================== Printing all word present in trie : dear deal do hen heat he |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
